17. Letter Combinations of a Phone Number

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)的总结:

回溯算法的核心是通过一步步构成可能的解,并且回溯不可能“解”来求所有或者部分解决方案的通用算法。其中“回溯”的具体意思就是将不可能“解”或者部分解的候选尽早地舍弃掉,“解”需要满足一定的限制条件

通用算法:

一般来说都会是个设置一个递归函数,函数的参数会携带一些当前的可能解的信息,根据这些参数得出可能解或者不可能而回溯,

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容