[LeetCode] 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.

[中文翻译] 给定一个数字字符串，返回数字可能代表的所有可能的字母组合。 下面给出了数字到字母的映射（就像电话上的按钮）。

输入： 数字字符串“23” 输出： [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

注意： 虽然上面的答案是按字典顺序，你的答案可以是任何你想要的顺序。

[解题思路] 显然可以把映射关系存成一个二维数组，然后写个十重for循环可以解决问题。但这不是一个通用的解法。

我们需要的是一个遍历所有可能的遍历方法。实际上，就是一个计数器，在最后一位不断地加1，如果枚举完了当前位，则当前位置零，进位，进位的时候考虑连续进位的情况。每一次计数，对应一个枚举的可能，实际上这就是按字典序在枚举。这样就能实现遍历所有的可能。

[C++代码]