leetcode17 电话号码的字母组合

方法1 if-else方法?

if-else方法的思路及其简单粗暴，如下图所示，以数字234为例，数字2所对应的字母是abc，数字3所对应的是def，数字4所对应的是ghi，最后所产生的结果就类似于我们中学所学过的树状图一样，从左到右的一组一组生成结果，首先取出数字2的第一个索引对应的a，然后紧接着添加数字3对应的第一个索引的字母d，然后再添加数字4所对应的ghi，分别组成adg、adh、adi，然后一直进行排列组合，直到把所有的结果都列举完，那么就程序就执行完了。

python完整代码：

class Solution:
    def letterCombinations(self, digits):
        # 获取输入数字串的长度
        n = len(digits)
        result = []  # 用于存储最终的字母组合结果
        if n == 0:
            return result  # 如果输入为空字符串，则直接返回空列表

        for i in range(n):
            self.AddString(result, digits[i])

        return result

    def AddString(self, result, t):  # 定义一个添加字符串的函数
        n = len(result)
        letters = ""
        if t == '2':
            letters = "abc"
        elif t == '3':
            letters = "def"
        elif t == '4':
            letters = "ghi"
        elif t == '5':
            letters = "jkl"
        elif t == '6':
            letters = "mno"
        elif t == '7':
            letters = "pqrs"
        elif t == '8':
            letters = "tuv"
        elif t == '9':
            letters = "wxyz"

        if n == 0:
            result.extend(list(letters))  # 如果结果集为空，直接添加第一个数字对应的字母
        else:
            temp_result = []
            for i in range(n):  # i表示第一个数字所对应的字母的位置
                for letter in letters:
                    # 将当前结果集中的每个组合与新的字母组合，得到新的结果集
                    temp_result.append(result[i] + letter)
            result[:] = temp_result  # 用新的结果集替换原有结果集


if __name__ == "__main__":
    solution = Solution()
    combinations = solution.letterCombinations("234")
    print(combinations)

c++完整代码：?

#include<iostream>
#include<vector>

using namespace std;

class Solution{
public:
    vector<string> letterCombinations(string digits){
        int n = digits.length();  //获取输入数字串的长度
        vector<string> result; //用于存储最终的字母组合结果
        if(n == 0){
            return result;
        }
        for(int i=0;i<n;++i){
            AddString(result, digits[i]);  // 调用添加字母函数
        }
        return result;
    }
private:
    void AddString(vector<string>& result, char digit){
        int n = result.size();
        string letters = "";
        if (digit == '2'){
            letters = "abc";
        } else if(digit == '3'){
            letters = "def";
        } else if(digit == '4'){
            letters = "ghi";
        } else if(digit == '5') {
            letters = "jkl";
        } else if(digit == '6'){
            letters = "mno";
        } else if(digit == '7'){
            letters = "pqrs";
        } else if(digit == '8'){
            letters = "tuv";
        } else if(digit == '9'){
            letters = "wxyz";
        }
        if (n == 0){
            for(char letter : letters){
                result.push_back(string(1, letter));
                // 如果结果集为空，直接添加第一个数字对应的字母
            }
        } else{
           vector<string> temp_result;
           for(int i = 0;i < n; ++i){
               for(char letter : letters){
                   // 将当前结果集中的每个组合与新的字母组合，得到新的结果集
                   temp_result.push_back(result[i] + letter);
               }
           }
           result = temp_result; // 用新的结果集替换原有结果集
        }
    }
};

int main(){
    Solution solution;
    vector<string> combinations = solution.letterCombinations("234");
    for(const auto& combination : combinations){
        cout << combination << endl;
    }
    return 0;
}

java完整代码：??

import java.util.List;
import java.util.ArrayList;
public class LetterCombinations {
    public List<String> letterCombinations(String digits) {
        // 获取输入数字串的长度
        int n = digits.length();
        // 用于存储最终的字母组合结果
        List<String> list = new ArrayList();
        // 如果输入为空字符串，则直接返回空列表
        if (n == 0) {
            return list;
        }

        // 遍历每个数字字符
        for (int i = 0; i < n; i++) {
            // 调用 StringAdd 函数处理每个数字对应的字母
            StringAdd(list, digits.charAt(i));
        }
        return list;
    }

    // 定义一个添加字符串的函数
    public void StringAdd(List<String> list, char t) {
        // 获取当前结果集的长度
        int n = list.size();
        if(t == '2'){  // 处理数字 2 对应的字母组合
            if(n==0){
                list.add("a");
                list.add("b");
                list.add("c");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 'a', 'b', 'c'，得到新的结果集
                    list.add(list.get(i)+"a");
                    list.add(list.get(i)+"b");
                    list.add(list.get(i)+"c");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
            // 3
        }else if(t == '3'){
            if(n==0){
                list.add("d");
                list.add("e");
                list.add("f");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 'd', 'e', 'f'，得到新的结果集
                    list.add(list.get(i)+"d");
                    list.add(list.get(i)+"e");
                    list.add(list.get(i)+"f");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
            // 4
        }else if(t == '4'){
            if(n==0){
                list.add("g");
                list.add("h");
                list.add("i");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 'g', 'h', 'i'，得到新的结果集
                    list.add(list.get(i)+"g");
                    list.add(list.get(i)+"h");
                    list.add(list.get(i)+"i");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
            // 5
        }else if(t == '5'){
            if(n==0){
                list.add("j");
                list.add("k");
                list.add("l");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 'j', 'k', 'l'，得到新的结果
                    list.add(list.get(i)+"j");
                    list.add(list.get(i)+"k");
                    list.add(list.get(i)+"l");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
            // 6
        }else if(t == '6'){
            if(n==0){
                list.add("m");
                list.add("n");
                list.add("o");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 'm', 'n', 'o'，得到新的结果
                    list.add(list.get(i)+"m");
                    list.add(list.get(i)+"n");
                    list.add(list.get(i)+"o");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
            // 7
        }else if(t == '7'){
            if(n==0){
                list.add("p");
                list.add("q");
                list.add("r");
                list.add("s");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 'p', 'q', 'r', 's'，得到新的结果
                    list.add(list.get(i)+"p");
                    list.add(list.get(i)+"q");
                    list.add(list.get(i)+"r");
                    list.add(list.get(i)+"s");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
            // 8
        }else if(t == '8'){
            if(n==0){
                list.add("t");
                list.add("u");
                list.add("v");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 't', 'u', 'v'，得到新的结果
                    list.add(list.get(i)+"t");
                    list.add(list.get(i)+"u");
                    list.add(list.get(i)+"v");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
            // 9
        }else if(t == '9'){
            if(n==0){
                list.add("w");
                list.add("x");
                list.add("y");
                list.add("z");
            }else{
                for(int i=0;i<n;i++){
                    // 遍历当前结果集，为每个组合添加 'w', 'x', 'y', 'z'，得到新的结果
                    list.add(list.get(i)+"w");
                    list.add(list.get(i)+"x");
                    list.add(list.get(i)+"y");
                    list.add(list.get(i)+"z");
                }
                for(int i=0;i<n;i++){
                    list.remove(0);
                }
            }
        }
    }
    public static void main(String[] args){
        LetterCombinations solution = new LetterCombinations();
        List<String> combinations = solution.letterCombinations("234");
        System.out.println(combinations);
    }
}

方法2 回溯法?

上面我们讨论了通过列举的方法生成结果，但是发现程序写起来实在是太长了，而且看着很low，那么此时我们就可以把数字组合里面每一个数字所对应的字母组合通过一个篮子（哈希表）存起来，要用哪个就拿哪一个，紧接着再通过回溯的方法进行解决，以下是chatgpt所回答的回溯算法：

回溯算法（Backtracking）是一种通过尝试所有可能的候选解并在找到可行解之前放弃部分（或全部）解空间的策略。在问题的解空间中，通过深度优先搜索，一步一步地探索各个可能的解，当发现当前的部分解不能满足问题的约束条件时，就放弃该部分解，回溯到上一步，继续搜索其他可能的解。

回溯算法通常采用递归的方式实现，每一层递归代表问题的一个阶段，通过递归的深入，逐步构建出问题的解。在搜索过程中，如果当前解不满足问题的条件，则回溯到上一步，尝试其他可能的选择。

典型的回溯问题包括组合问题、排列问题、子集问题等。回溯算法通常用于解决组合优化问题，其中问题的解是某种组合的集合，而且问题通常可以分解为多个子问题，通过递归地解决子问题来构建整体的解。

关键特点：

1. 状态空间树： 回溯算法可以通过状态空间树的形式进行表示，每个节点代表问题的一个阶段，树的每一层对应算法的一个递归调用。
2. 深度优先搜索： 回溯算法采用深度优先搜索的策略，即一条路走到底，如果发现当前路径不能满足问题的条件，就回溯到上一步。
3. 剪枝： 在搜索的过程中，可以通过剪枝来减少搜索空间，提高效率。当发现当前部分解无法满足问题的条件时，可以提前结束搜索。

经典的回溯问题包括八皇后问题、0-1背包问题、图的着色问题等。回溯算法的复杂度通常比较高，因此在设计时需要注意优化搜索空间以提高效率。

但是本题不存在不可行的解，所以通过穷举的方法就可以实现。该方法的思路和上述的方法基本上是一致的。

python完整代码：

class Solution:
    def letterCombinations(self, digits):
        # 如果输入为空，则直接返回空列表
        if not digits:
            return list()
        # 定义电话号码到字母的映射关系
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        def backtrack(index):
           # 当前组合字符串长度等于输入数字串长度时，将其加入结果集
           if index == len(digits):
               combinations.append("".join(combination))  # 获取当前数字对应的字母集合
           else:
               digit = digits[index]  # 将当前字母加入组合字符串，递归调用下一层
               for letter in phoneMap[digit]:
                   combination.append(letter)
                   backtrack(index + 1)
                   # pop()函数用于移除列表中的一个元素(默认最后一个元素)，并且返回该元素的值
                   combination.pop()  # 当combinations里面存有adg，紧接着执行for letter in phoneMap[digit]:其中digit=4

        combination = list()  # 初始化组合列表和当前组合字符串
        combinations = list()
        backtrack(0)  # 初始调用回溯函数
        return combinations

if __name__ == "__main__":
    # 创建 Solution 对象
    solution = Solution()
    # 调用 letterCombinations 函数并输出结果
    combinations = solution.letterCombinations("234")
    print(combinations)

class Solution:
    def letterCombinations(self, digits):
        # 如果输入为空，则直接返回空列表
        if not digits:
            return list()
        # 定义电话号码到字母的映射关系
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        def backtrack(index):
           # 当前组合字符串长度等于输入数字串长度时，将其加入结果集
           if index == len(digits):
               combinations.append("".join(combination))  # 获取当前数字对应的字母集合
           else:
               digit = digits[index]  # 将当前字母加入组合字符串，递归调用下一层
               for letter in phoneMap[digit]:
                   combination.append(letter)
                   backtrack(index + 1)
                   # pop()函数用于移除列表中的一个元素(默认最后一个元素)，并且返回该元素的值
                   combination.pop()  # 当combinations里面存有adg，紧接着执行for letter in phoneMap[digit]:其中digit=4

        combination = list()  # 初始化组合列表和当前组合字符串
        combinations = list()
        backtrack(0)  # 初始调用回溯函数
        return combinations

if __name__ == "__main__":
    # 创建 Solution 对象
    solution = Solution()
    # 调用 letterCombinations 函数并输出结果
    combinations = solution.letterCombinations("234")
    print(combinations)

c++完整代码：

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

class Solution{
public:
    vector<string> letterCombination(string digits){
        unordered_map<char, string> phoneMap = { // 定义数字对应的字母映射关系
                {'2', "abc"},
                {'3', "def"},
                {'4', "ghi"},
                {'5', "jkl"},
                {'6', "mno"},
                {'7', "pqrs"},
                {'8', "tuv"},
                {'9', "wxyz"}
        };
        // 处理特殊情况，如果输入为空字符串，则直接返回空列表
        if(digits.empty()){
            return vector<string> ();
        }
        // 用于存储最终的字母组合结果
        vector<string> result;
        // 回溯函数，参数分别为当前数字索引和当前已形成的组合字符串
        backtrack(digits,0,"",phoneMap,result);  
        //可以试试index等于1是什么结果，就能明白该参数具体指的是什么
        
        return result;
    }
private:
    // index ---> 数字所对应字母的索引
    void backtrack(const string& digits, int index, const string& path,
                   const unordered_map<char, string>& phoneMap, vector<string>& result){
        // 如果当前组合字符串的长度等于输入数字串的长度，将其加入结果集
        if(index == digits.length()){
            result.push_back(path);
            return;
        }
        // 获取当前数字对应的字母集合
        char currentDigit = digits[index];
        const string& letters = phoneMap.at(currentDigit);
        // 遍历当前数字对应的字母集合，进行递归回溯
        for(char letter : letters){
            // 将当前字母加入组合字符串，递归调用下一层
            backtrack(digits, index + 1, path + letter, phoneMap, result);
        }
    }
};

int main(){
    // 创建 Solution 对象
    Solution solution;
    // 调用 letterCombinations 函数并输出结果
    vector<string> combinations = solution.letterCombination("234");
    for(const string& combination : combinations){
        cout << combination << "" << endl;
    }
    return 0;
}

java完整代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class letterCombinations_1 {
    public List<String> letterCombinations(String digits) {
        Map<Character, String> phoneMap = new HashMap<>(); // 定义数字对应的字母映射关系
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        // 处理特殊情况，如果输入为空字符串，则直接返回空列表
        if (digits == null || digits.isEmpty()) {
            return new ArrayList<>();
        }

        // 用于存储最终的字母组合结果
        List<String> result = new ArrayList<>();
        // 回溯函数，参数分别为当前数字索引和当前已形成的组合字符串
        backtrack(digits, 0, "", phoneMap, result);

        return result;
    }

    private void backtrack(String digits, int index, String path,
                           Map<Character, String> phoneMap, List<String> result) {
        // 如果当前组合字符串的长度等于输入数字串的长度，将其加入结果集
        if (index == digits.length()) {
            result.add(path);
            return;
        }

        // 获取当前数字对应的字母集合
        char currentDigit = digits.charAt(index);
        String letters = phoneMap.get(currentDigit);

        // 遍历当前数字对应的字母集合，进行递归回溯
        for (char letter : letters.toCharArray()) {
            // 将当前字母加入组合字符串，递归调用下一层
            backtrack(digits, index + 1, path + letter, phoneMap, result);
        }
    }

    public static void main(String[] args) {
        // 创建 Solution 对象
        letterCombinations_1 solution = new letterCombinations_1();
        // 调用 letterCombinations 函数并输出结果
        List<String> combinations = solution.letterCombinations("234");
        for (String combination : combinations) {
            System.out.println(combination);
        }
    }
}