Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below:
Input:Digit string "23" Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
解答:
与22-generate parentheses一样,和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母,并加入当前combination中传到下一层递归。
这里我要重点做一下回溯(backtracking)的总结:
回溯算法的核心是通过一步步构成可能的解,并且回溯不可能“解”来求所有或者部分解决方案的通用算法。其中“回溯”的具体意思就是将不可能“解”或者部分解的候选尽早地舍弃掉,“解”需要满足一定的限制条件
通用算法:
一般来说都会是个设置一个递归函数,函数的参数会携带一些当前的可能解的信息,根据这些参数得出可能解或者不可能而回溯,