接月初算法系列，思路：
滑动窗口 => BFS、DFS => 回溯法，各个经典！
- 《温故知新 —— Sliding Window》
- 《辛辣天塞！滑动窗口之【和的最大值】&【最大值集合】》
- 《keep move！滑动窗口中位数与滑动魔方》
- 《好的，BFS，又学废了！》
- 《好的，DFS，也学废了！》
- 《从 DFS 到回溯法，再看 N 皇后问题》
本篇将继续深入回溯法！
经典题目之：电话号码的字母组合
题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1： 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2： 输入：digits = "" 输出：[] 示例 3： 输入：digits = "2" 输出：["a","b","c"]
解题思路：
- 用map保存数字对应的字母
- 从第一个数字开始遍历，取一个字母，然后从第二个数字，取一个字母，第三个数字，取一个字母...
- 数字遍历完了，将拼接好的字符串str加入结果数组res
- 回溯，修改最后一个数字对应的字母
- 重复2-4过程
JS 实现：
var letterCombinations = function (digits) { // 为空特殊处理 if (digits.length === 0) return []; let numMap = new Map([ ['0', ''], ['1', ''], ['2', 'abc'], ['3', 'def'], ['4', 'ghi'], ['5', 'jkl'], ['6', 'mno'], ['7', 'pqrs'], ['8', 'tuv'], ['9', 'wxyz'] ]) let res = []; dfs("", digits); return res; function dfs(str, digit) { // 如果字符串为空了，将拼接好的字符加入数组 if (digit.length === 0) res.push(str); else { // 拿到字符串第一个字符，拿到其对应的数字 let numstr = numMap.get(digit[0]); // 对可能性进行组合 for (let i = 0; i < numstr.length; i++) { str += numstr[i]; // 递归组好的 str和下一段字符串 dfs(str, digit.slice(1)) // 回溯 str = str.slice(0, -1); } } } };
小结：回溯本质是暴力搜索，在问题的解空间树中，用 DFS 的方式，从根节点出发搜索整个解空间。 如果要找出所有的解，则要搜索整个子树，如果只用找出一个解，则搜到一个解就可以结束搜索。
“找出所有可能的组合”的问题，适合用回溯算法。
OK，以上就是本篇分享~ 撰文不易，点赞鼓励👍👍👍
我是掘金安东尼，公众号同名，日拱一卒、日掘一金，再会~
