17. Letter Combinations of a Phone Number Medium

1/**
2 * [17] Letter Combinations of a Phone Number
3 *
4 * Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
5 * A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
6 * <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png" style="width: 200px; height: 162px;" />
7 *  
8 * Example 1:
9 * 
10 * Input: digits = "23"
11 * Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
12 * 
13 * Example 2:
14 * 
15 * Input: digits = ""
16 * Output: []
17 * 
18 * Example 3:
19 * 
20 * Input: digits = "2"
21 * Output: ["a","b","c"]
22 * 
23 *  
24 * Constraints:
25 * 
26 * 0 <= digits.length <= 4
27 * digits[i] is a digit in the range ['2', '9'].
28 * 
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
33// discuss: https://leetcode.com/problems/letter-combinations-of-a-phone-number/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37impl Solution {
38    const KEYS: [&'static str; 10] = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
39
40    pub fn letter_combinations(digits: String) -> Vec<String> {
41        let mut result = vec![];
42        if digits.len() == 0 {
43            return result;
44        }
45
46        Self::combination(&"".to_string(), &digits, 0, &mut result);
47        result
48    }
49
50    fn combination(prefix: &String, digits: &String, offset: usize, result: &mut Vec<String>) {
51        if offset >= digits.len() {
52            result.push(prefix.clone());
53            return;
54        }
55
56        let all = Self::KEYS[digits.chars().nth(offset).unwrap() as usize - '0' as usize];
57        for s in all.chars() {
58            let mut copy = prefix.clone();
59            copy.push(s);
60            Self::combination(&copy, digits, offset + 1, result);
61        }
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_17() {
73        println!("Got result {:#?}", Solution::letter_combinations("23".to_owned()));
74    }
75}
76