leetcode_rust/problems_cn/p000_0xx/
p000_017.rs

1//! # 问题描述
2//!
3//! 给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。答案可以按**任意顺序**
4//! 返回。
5//! 
6//! 给出数字到字母的映射如下（与电话按键相同）。注意 `1` 不对应任何字母。
7//! 
8//! ![](https://eastwind-cdn.dongs.xyz/image/20230224010445.png?w=256)
9//! 
10//! 示例 1：
11//! 
12//! ```plain
13//! 输入：digits = "23"
14//! 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
15//! ```
16//! 
17//! 示例 2：
18//! 
19//! ```plain
20//! 输入：digits = ""
21//! 输出：[]
22//! ```
23//! 
24//! 示例 3：
25//! 
26//! ```plain
27//! 输入：digits = "2"
28//! 输出：["a","b","c"]
29//! ```
30//! 
31//! 提示：
32//! 
33//! - `0 $\leqslant$ digits.length $\leqslant$ 4`
34//! - `digits[i]` 是范围 `['2', '9']` 的一个数字。
35//! 
36//! 来源: <https://leetcode.cn/problems/letter-combinations-of-a-phone-number/>
37
38////////////////////////////////////////////////////////////////////////////////
39
40/// 电话号码的字母组合
41///
42/// # 参数
43/// * `digits` - 输入的数字序列
44///
45/// # 示例
46///
47/// ```rust
48/// use leetcode_rust::problems_cn::p000_0xx::p000_017::letter_combinations;
49///
50/// let input = String::from("2");
51/// let output = letter_combinations(input);
52/// assert_eq!(output, vec!["a", "b", "c"]);
53/// ```
54pub fn letter_combinations(digits: String) -> Vec<String> {
55    // letter_combinations_by_match_control_flow(digits)
56    letter_combinations_by_pre_allocation(digits)
57    // letter_combinations_by_pre_allocation_v2(digits)
58}
59
60/// Match structure to get the letters for each digit
61///
62/// # Arguments
63/// - `digits` - input digits
64#[allow(dead_code)]
65fn letter_combinations_by_match_control_flow(digits: String) -> Vec<String> {
66    use std::str;
67    let mut res: Vec<String> = vec![];
68    for digit in digits.as_bytes() {
69        let letters = match *digit {
70            b'2' => "abc",
71            b'3' => "def",
72            b'4' => "ghi",
73            b'5' => "jkl",
74            b'6' => "mno",
75            b'7' => "pqrs",
76            b'8' => "tuv",
77            b'9' => "wxyz",
78            _ => "",
79        }
80        .as_bytes();
81
82        if res.len() > 0 {
83            let mut temp_res = vec![];
84            for partial in res {
85                for letter in letters {
86                    let mut new_partial = partial.clone();
87                    new_partial.push(*letter as char);
88                    temp_res.push(new_partial);
89                }
90            }
91            res = temp_res;
92        } else {
93            res = letters
94                .iter()
95                .map(|l| str::from_utf8(vec![*l].as_slice()).unwrap().to_string())
96                .collect();
97        }
98    }
99
100    res
101}
102
103/// Create a vector of bytes representing each digit in advance. Save memory usage
104/// significantly.
105///
106/// # Arguments
107/// - `digits` - input digits
108#[allow(dead_code)]
109fn letter_combinations_by_pre_allocation(digits: String) -> Vec<String> {
110    use std::str;
111
112    let digits_to_letters: Vec<&[u8]> =
113        vec!["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
114            .iter()
115            .map(|s| s.as_bytes())
116            .collect();
117
118    let mut res: Vec<String> = vec![];
119    for digit in digits.as_bytes() {
120        let letters = digits_to_letters[(*digit - b'2') as usize];
121
122        if res.len() > 0 {
123            let mut temp_res = vec![];
124            for partial in res {
125                for letter in letters {
126                    let mut new_partial = partial.clone();
127                    new_partial.push(*letter as char);
128                    temp_res.push(new_partial);
129                }
130            }
131            res = temp_res;
132        } else {
133            let mut temp: Vec<String> = letters
134                .iter()
135                .map(|l| str::from_utf8(vec![*l].as_slice()).unwrap().to_string())
136                .collect();
137            res.append(&mut temp);
138        }
139    }
140
141    res
142}
143
144/// Create a vector of bytes representing each digit in advance. Save memory
145/// usage significantly. Simplified expression but may cause a little more
146/// memory consumption.
147///
148/// # Arguments
149/// - `digits` - input digits
150#[allow(dead_code)]
151fn letter_combinations_by_pre_allocation_v2(digits: String) -> Vec<String> {
152    use std::str;
153
154    let digits_to_letters: Vec<&[u8]> =
155        vec!["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
156            .iter()
157            .map(|s| s.as_bytes())
158            .collect();
159
160    let mut res: Vec<String> = vec![];
161    for digit in digits.as_bytes() {
162        let letters = digits_to_letters[(*digit - b'2') as usize];
163
164        res = if res.len() == 0 {
165            letters
166                .iter()
167                .map(|l| str::from_utf8(&[*l]).unwrap().to_string())
168                .collect()
169        } else {
170            let mut temp_res = vec![];
171            for partial in res {
172                for letter in letters {
173                    temp_res.push(partial.clone() + str::from_utf8(&[*letter]).unwrap());
174                }
175            }
176            temp_res
177        };
178    }
179
180    res
181}
182
183#[cfg(test)]
184mod tests {
185    use super::letter_combinations;
186    #[test]
187    fn test_letter_combinations() {
188        assert_eq!(
189            letter_combinations(String::from("23")),
190            vec!["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
191        );
192        assert_eq!(letter_combinations(String::from("")), Vec::<String>::new());
193        assert_eq!(letter_combinations(String::from("2")), vec!["a", "b", "c"]);
194    }
195}
leetcode_rust/problems_cn/p000_0xx/p000_017.rs

leetcode_rust/problems_cn/p000_0xx/
p000_017.rs
