给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
img
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
|
示例 2：
示例 3：
输入：digits = "2"
输出：["a","b","c"]
|
提示：
0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。
思路
一道常规的dfs题目。使用Java，StringBuffer类可以很好地插入、删除和构建字符串。
class Solution {
public Map<Integer, String[]> charMap;
public List<String> ans;
public String digits;
public List<String> letterCombinations(String digits) {
charMap = new HashMap<>();
ans = new ArrayList<>();
this.digits = digits;
if (digits.length() == 0) return ans;
charMap.put(2, new String[] {"a", "b", "c"});
charMap.put(3, new String[] {"d", "e", "f"});
charMap.put(4, new String[] {"g", "h", "i"});
charMap.put(5, new String[] {"j", "k", "l"});
charMap.put(6, new String[] {"m", "n", "o"});
charMap.put(7, new String[] {"p", "q", "r", "s"});
charMap.put(8, new String[] {"t", "u", "v"});
charMap.put(9, new String[] {"w", "x", "y", "z"});
dfs(0, new StringBuffer());
return ans;
}
public void dfs(int numIdx, StringBuffer buffer) {
if (numIdx == digits.length()) {
ans.add(buffer.toString());
return;
}
System.out.println(digits.charAt(numIdx) - '0');
String[] chars = charMap.get(digits.charAt(numIdx) - '0');
for (int i = 0; i < chars.length; i++) {
buffer.append(chars[i]);
dfs(numIdx+1, buffer);
buffer.delete(buffer.length() - 1, buffer.length());
}
}
}
|
算法复杂度
