1
2

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

1
2

输入：digits = ""
输出：[]

1
2

输入：digits = "2"
输出：["a","b","c"]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// @lc code=start
const MAPPING: [std::ops::RangeInclusive<u8>; 8] = [
    (b'a'..=b'c'),
    (b'd'..=b'f'),
    (b'g'..=b'i'),
    (b'j'..=b'l'),
    (b'm'..=b'o'),
    (b'p'..=b's'),
    (b't'..=b'v'),
    (b'w'..=b'z'),
];

impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        digits.as_bytes().iter().fold(
            if digits.is_empty() {
                Vec::new()
            } else {
                vec![String::new()]
            },
            |acc, &x| {
                acc.iter().flat_map(|s| {
                    std::iter::repeat(s)
                        .zip(MAPPING[(x-b'2') as usize].clone())
                        .map(|(s,b)| {
                            s.chars()
                             .chain(std::iter::once(b as char))
                             .collect()
                        })
                        .collect::<Vec<_>>()
                })
                .collect()
            },
        )
    }
}
// @lc code=end

struct Solution;

#[test]
fn it_works() {
    assert_eq!( Solution::letter_combinations("23".to_string()),
                vec!["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    vector<string> result;
    vector<string> letters = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    /*
    * ## 解题思路
    * * 回溯法
    * 1. 依次尝试每个数字对应的各个字母
    */
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) {
            return result;
        }
        string path = "";
        dfs(digits, path, 0);
        return result;
    }

    //
    void dfs(string& digits, string& path, int i) {
        if (i>=digits.length()){
            result.push_back(path);
            return;
        }

        for(char c: letters[digits[i]-'2']) {
            path.push_back(c);
            dfs(digits, path, i+1);
            path.pop_back();
        }
    }
};