解题思路

就是遍历digits，然后将每种可能遍历一遍。

  • Go要注意，回溯要将数组定义在最外面，不然修改不到。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letter = {'2': "abc", '3': "def", '4': "ghi", '5': "jkl", '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"}
        answer = []
        if not digits: return answer
        def backtracking(start: int, temp: str) -> None:
            if len(temp) == len(digits):
                answer.append(temp)
                return
            for i in range(start, len(digits)):
                for c in letter[digits[i]]:
                    temp += c
                    backtracking(i + 1, temp)
                    temp = temp[: len(temp) - 1]
        
        backtracking(0, "")
        return answer

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
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> combinations;
        if (digits.empty()) {
            return combinations;
        }
        unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string combination;
        backtrack(combinations, phoneMap, digits, 0, combination);
        return combinations;
    }

    void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
        if (index == digits.length()) {
            combinations.push_back(combination);
        } else {
            char digit = digits[index];
            const string& letters = phoneMap.at(digit);
            for (const char& letter: letters) {
                combination.push_back(letter);
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};

Go

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
var phoneMap map[string]string = map[string]string{
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}

var combinations []string

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    combinations = []string{}
    backtrack(digits, 0, "")
    return combinations
}

func backtrack(digits string, index int, combination string) {
    if index == len(digits) {
        combinations = append(combinations, combination)
    } else {
        digit := string(digits[index])
        letters := phoneMap[digit]
        lettersCount := len(letters)
        for i := 0; i < lettersCount; i++ {
            backtrack(digits, index + 1, combination + string(letters[i]))
        }
    }
}