LeetCode - 17 电话号码的字母组合
题目来源
17. 电话号码的字母组合 - 力扣（LeetCode）
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例1
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例2
输入：digits = ""
输出：[]
示例3
输入：digits = "2"
输出：["a","b","c"]
提示
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
题目解析
本题是一个组合问题，可以使用回溯算法解题。
什么是组合问题？
以示例一为例：digits = "23"，其中：
- "2" 对应的可选字母有：['a', 'b', 'c']
- “3” 对应的可选字母有：['d', 'e', 'f']
因此 "23" 对应的组合有："ad"、"ae"、"af"、"bd"、"be"、"bf"、"cd"、"ce"、"cf"
如果画图表示的话，可以发现组合问题的求解过程，可以形成一个树形结构。
该树形结构的每一条根到叶子节点的路径都对应一个组合。
因此，如果我们可以遍历出该树形结构的每一条分支，那么就能求出所有组合。
我们可以使用深搜DFS来遍历出树的每一条分支，而深搜本质来说是一种回溯算法。关于回溯算法可以看下：
带你学透回溯算法（理论篇）| 回溯法精讲！_哔哩哔哩_bilibili
C源码实现
/*** Note: The returned array must be malloced, assume caller calls free().*/
char *dic[] = {"", "", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};// 记录所有组合
char **results;
int results_size;// 用于记录某个组合的临时容器
char path[5] = {'\0'};
int path_size = 0;/*** 回溯算法* @param index 表示当前找的是组合的第index个元素* @param digits 原始串*/
void dfs(int index, char *digits) {if (path_size == strlen(digits)) { // 组合元素数量达标results[results_size] = (char *) calloc(5, sizeof(char));strcpy(results[results_size++], path); // 将临时组合记录进结果集return;}// 第index层可选的字母char *letters = dic[digits[index] - '0'];// 第index层的每一个字母都参与形成组合for (int i = 0; i < strlen(letters); i++) {path[path_size++] = letters[i]; // 字母letters[i]加入组合dfs(index + 1, digits); // 继续进入下层path[--path_size] = '\0'; // 回溯}
}char **letterCombinations(char *digits, int *returnSize) {// digits长度最大4, 每个数字最多对应4个字母，因此最多产生 4 * 4 * 4 * 4 个组合results = (char **) calloc(256, sizeof(char *));results_size = 0;if (strlen(digits) != 0) {dfs(0, digits);}*returnSize = results_size;return results;
}C++算法源码
class Solution {
public:vector<string> dic = {"", "", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> letterCombinations(string digits) {vector<string> results;if (!digits.empty()) {dfs(0, "", digits, results);}return results;}/*** 回溯算法* @param index 表示当前找的是组合的第index个元素* @param path 用于记录某个组合的临时容器* @param digits 原始串* @param results 记录所有组合的结果集*/void dfs(int index, string path, string digits, vector<string> &results) {if (path.length() == digits.length()) { // 组合元素数量达标results.emplace_back(path); // 将临时组合记录进结果集return;}// 第index层可选的字母string letters = dic[digits[index] - '0'];// 第index层的每一个字母都参与形成组合for (int i = 0; i < letters.length(); i++) {path.push_back(letters[i]); // 字母letters[i]加入组合dfs(index + 1, path, digits, results); // 继续进入下层path.pop_back(); // 回溯}}
};Java源码实现
class Solution {String[] dic = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {ArrayList<String> results = new ArrayList<>();if (!digits.isEmpty()) {dfs(0, new StringBuilder(), digits, results);}return results;}/*** 回溯算法** @param index 表示当前找的是组合的第index个元素* @param path 用于记录某个组合的临时容器* @param digits 原始串* @param results 记录所有组合的结果集*/public void dfs(int index, StringBuilder path, String digits, ArrayList<String> results) {if (path.length() == digits.length()) { // 组合元素数量达标results.add(path.toString()); // 将临时组合记录进结果集return;}// 第index层可选的字母String letters = dic[digits.charAt(index) - '0'];// 第index层的每一个字母都参与形成组合for (int j = 0; j < letters.length(); j++) {path.append(letters.charAt(j)); // 字母letters[i]加入组合dfs(index + 1, path, digits, results); // 继续进入下层path.deleteCharAt(path.length() - 1); // 回溯}}
}Python源码实现
dic = ("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")def dfs(index, path, digits, results):"""回溯算法:param index: 表示当前找的是组合的第index个元素:param path: 用于记录某个组合的临时容器:param digits: 原始串:param results: 记录所有组合的结果集:return: void"""if len(path) == len(digits): # 组合元素数量达标results.append("".join(path)) # 将临时组合记录进结果集return# 第index层可选的字母letters = dic[int(digits[index])]# 第index层的每一个字母都参与形成组合for i in range(len(letters)):path.append(letters[i]) # 字母letters[i]加入组合dfs(index + 1, path, digits, results) # 继续进入下层path.pop() # 回溯class Solution(object):def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""results = []if len(digits) > 0:dfs(0, [], digits, results)return results
JavaScript源码实现
/*** @param {string} digits* @return {string[]}*/
const dic = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];var letterCombinations = function (digits) {const results = [];if (digits.length > 0) {dfs(0, [], digits, results);}return results;
};/*** 回溯算法* @param {*} index 表示当前找的是组合的第index个元素* @param {*} path 用于记录某个组合的临时容器* @param {*} digits 原始串* @param {*} results 记录所有组合的结果集* @returns void*/
function dfs(index, path, digits, results) {if (path.length == digits.length) { // 组合元素数量达标results.push(path.join("")); // 将临时组合记录进结果集return;}// 第index层可选的字母const letters = dic[parseInt(digits[index])];for (let i = 0; i < letters.length; i++) {path.push(letters[i]); // 字母letters[i]加入组合dfs(index + 1, path, digits, results); // 继续进入下层path.pop(); // 回溯}
}