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 resultdef 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=4combination = list()  # 初始化组合列表和当前组合字符串combinations = list()backtrack(0)  # 初始调用回溯函数return combinationsif __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=4combination = list()  # 初始化组合列表和当前组合字符串combinations = list()backtrack(0)  # 初始调用回溯函数return combinationsif __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);}}
}