题目描述
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
思路
感觉像是对树的深度优先搜索,假设数字是 23
,那它的大概结构是:
flowchart TD
A["root"]
A-->B["a"]
A-->C["b"]
A-->D["c"]
B-->E["d"]
B-->F["e"]
B-->G["f"]
C-->H["..."]
这种感觉,首先考虑写一个 DFS:
那么接下来考虑怎样保存上一次 dfs 的状态。因为字符串的长度就是 digits
的长度,因此我们可以新建一个临时数组保存当前的树,并在每次更新的是否赋值。那什么时候结束呢?当 idx==n
的时候代表一次 DFS 结束了,此时临时数组的值就是答案(的一部分)。
另外还要注意特殊值,输入为空字符串时返回 []
。
最终代码:
想得太多