这是 LeetCode 上的「17. 电话号码的字母组合」,难度为 Medium。
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明: 尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
对于字符串 ds
中的每一位数字,都有其对应的字母映射数组。
在 DFS 中决策每一位数字应该对应哪一个字母,当决策的位数 i == n
,代表整个 ds
字符串都被决策完毕,将决策结果添加到结果集:
class Solution {
Map<String, String[]> map = new HashMap<>(){{
put("2", new String[]{"a", "b", "c"});
put("3", new String[]{"d", "e", "f"});
put("4", new String[]{"g", "h", "i"});
put("5", new String[]{"j", "k", "l"});
put("6", new String[]{"m", "n", "o"});
put("7", new String[]{"p", "q", "r", "s"});
put("8", new String[]{"t", "u", "v"});
put("9", new String[]{"w", "x", "y", "z"});
}};
public List<String> letterCombinations(String ds) {
int n = ds.length();
List<String> ans = new ArrayList<>();
if (n == 0) return ans;
StringBuilder sb = new StringBuilder();
dfs(ds, 0, n, sb, ans);
return ans;
}
void dfs(String ds, int i, int n, StringBuilder sb, List<String> ans) {
if (i == n) {
ans.add(sb.toString());
return;
}
String key = ds.substring(i, i + 1);
String[] all = map.get(key);
for (String item : all) {
sb.append(item);
dfs(ds, i + 1, n, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
}
}
n
代表字符串 ds
的长度,一个数字最多对应 4 个字符(7 对应 “pqrs"),即每个数字最多有 4 个字母需要被决策。复杂度为这是一道「回溯算法」的经典题。
没有思维的上的难度,考察的是对「回溯算法」的基本理解。
通常我们会如何联想到「回溯算法」呢?基本上对于那些要枚举所有方案的题目,其实都应该先想到「回溯算法」。
「回溯算法」从算法定义上来说,不一定要用 DFS 实现,但通常结合 DFS 来做,难度是最低的。
回溯算法的基本模板是:
void dfs(路径, 选择列表, 结果集):
if (满足结束条件) {
结果集.add(路径);
return;
}
for (选择 in 选择列表) {
做选择;
dfs(路径’, 选择列表, 结果集);
撤销选择;
}
这是我们「刷穿 LeetCode」系列文章的第 No.17
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
「在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。」