leetcode_rust/problems/p000_0xx/
p000_017.rs

1//! # Description
2//!
3//! Given a string containing digits from `2-9` inclusive, return all possible
4//! letter combinations that the number could represent. Return the answer in
5//! any order.
6//!
7//! A mapping of digits to letters (just like on the telephone buttons) is
8//! given below. Note that `1` does not map to any letters.
9//!
10//! ![](https://eastwind-cdn.dongs.xyz/image/20230224010445.png?w=256)
11//!
12//! Example 1:
13//!
14//! ```plain
15//! Input: digits = "23"
16//! Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
17//! ```
18//!
19//! Example 2:
20//!
21//! ```plain
22//! Input: digits = ""
23//! Output: []
24//! ```
25//!
26//! Example 3:
27//!
28//! ```plain
29//! Input: digits = "2"
30//! Output: ["a","b","c"]
31//! ```
32//!
33//! Constraints:
34//!
35//! - `0 $\leqslant$ digits.length $\leqslant$ 4`
36//! - `digits[i]` is a digit in the range `['2', '9']`.
37//!
38//! Sources: <https://leetcode.com/problems/letter-combinations-of-a-phone-number/>
39
40////////////////////////////////////////////////////////////////////////////////
41
42/// Letter Combinations of a Phone Number
43///
44/// # Arguments
45/// * `digits` - input digits
46///
47/// # Examples
48///
49/// ```rust
50/// use leetcode_rust::problems::p000_0xx::p000_017::letter_combinations;
51///
52/// let input = String::from("2");
53/// let output = letter_combinations(input);
54/// assert_eq!(output, vec!["a", "b", "c"]);
55/// ```
56pub fn letter_combinations(digits: String) -> Vec<String> {
57    // letter_combinations_by_match_control_flow(digits)
58    letter_combinations_by_pre_allocation(digits)
59    // letter_combinations_by_pre_allocation_v2(digits)
60}
61
62/// Match structure to get the letters for each digit
63///
64/// # Arguments
65/// - `digits` - input digits
66#[allow(dead_code)]
67fn letter_combinations_by_match_control_flow(digits: String) -> Vec<String> {
68    use std::str;
69    let mut res: Vec<String> = vec![];
70    for digit in digits.as_bytes() {
71        let letters = match *digit {
72            b'2' => "abc",
73            b'3' => "def",
74            b'4' => "ghi",
75            b'5' => "jkl",
76            b'6' => "mno",
77            b'7' => "pqrs",
78            b'8' => "tuv",
79            b'9' => "wxyz",
80            _ => "",
81        }
82        .as_bytes();
83
84        if res.len() > 0 {
85            let mut temp_res = vec![];
86            for partial in res {
87                for letter in letters {
88                    let mut new_partial = partial.clone();
89                    new_partial.push(*letter as char);
90                    temp_res.push(new_partial);
91                }
92            }
93            res = temp_res;
94        } else {
95            res = letters
96                .iter()
97                .map(|l| str::from_utf8(vec![*l].as_slice()).unwrap().to_string())
98                .collect();
99        }
100    }
101
102    res
103}
104
105/// Create a vector of bytes representing each digit in advance. Save memory usage
106/// significantly.
107///
108/// # Arguments
109/// - `digits` - input digits
110#[allow(dead_code)]
111fn letter_combinations_by_pre_allocation(digits: String) -> Vec<String> {
112    use std::str;
113
114    let digits_to_letters: Vec<&[u8]> =
115        vec!["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
116            .iter()
117            .map(|s| s.as_bytes())
118            .collect();
119
120    let mut res: Vec<String> = vec![];
121    for digit in digits.as_bytes() {
122        let letters = digits_to_letters[(*digit - b'2') as usize];
123
124        if res.len() > 0 {
125            let mut temp_res = vec![];
126            for partial in res {
127                for letter in letters {
128                    let mut new_partial = partial.clone();
129                    new_partial.push(*letter as char);
130                    temp_res.push(new_partial);
131                }
132            }
133            res = temp_res;
134        } else {
135            let mut temp: Vec<String> = letters
136                .iter()
137                .map(|l| str::from_utf8(vec![*l].as_slice()).unwrap().to_string())
138                .collect();
139            res.append(&mut temp);
140        }
141    }
142
143    res
144}
145
146/// Create a vector of bytes representing each digit in advance. Save memory
147/// usage significantly. Simplified expression but may cause a little more
148/// memory consumption.
149///
150/// # Arguments
151/// - `digits` - input digits
152#[allow(dead_code)]
153fn letter_combinations_by_pre_allocation_v2(digits: String) -> Vec<String> {
154    use std::str;
155
156    let digits_to_letters: Vec<&[u8]> =
157        vec!["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
158            .iter()
159            .map(|s| s.as_bytes())
160            .collect();
161
162    let mut res: Vec<String> = vec![];
163    for digit in digits.as_bytes() {
164        let letters = digits_to_letters[(*digit - b'2') as usize];
165
166        res = if res.len() == 0 {
167            letters
168                .iter()
169                .map(|l| str::from_utf8(&[*l]).unwrap().to_string())
170                .collect()
171        } else {
172            let mut temp_res = vec![];
173            for partial in res {
174                for letter in letters {
175                    temp_res.push(partial.clone() + str::from_utf8(&[*letter]).unwrap());
176                }
177            }
178            temp_res
179        };
180    }
181
182    res
183}
184
185#[cfg(test)]
186mod tests {
187    use super::letter_combinations;
188    #[test]
189    fn test_letter_combinations() {
190        assert_eq!(
191            letter_combinations(String::from("23")),
192            vec!["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
193        );
194        assert_eq!(letter_combinations(String::from("")), Vec::<String>::new());
195        assert_eq!(letter_combinations(String::from("2")), vec!["a", "b", "c"]);
196    }
197}
leetcode_rust/problems/p000_0xx/p000_017.rs

leetcode_rust/problems/p000_0xx/
p000_017.rs
