力扣 17. 电话号码的字母组合
题目描述:
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
解析:
回溯法
Java:
class Solution {
List<String> list = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() == 0) {
return list;
}
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backTrack(digits, numString, 0);
return list;
}
StringBuilder temp = new StringBuilder();
public void backTrack(String digits, String[] numString, int num) {
if(num == digits.length()) {
list.add(temp.toString());
return;
}
String str = numString[digits.charAt(num) - '0'];
for(int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i));
backTrack(digits, numString, num + 1);
temp.deleteCharAt(temp.length() - 1);
}
}
}
JavaScript:
var letterCombinations = function(digits) {
const k = digits.length;
const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
if(!k) {
return [];
}
if(k === 1) {
return map[digits].split("");
}
const res = [], path = [];
backTrack(digits, k, 0);
return res;
function backTrack(n, k, a) {
if(path.length === k) {
res.push(path.join(""));
return;
}
for(const v of map[n[a]]) {
path.push(v);
backTrack(n, k, a + 1);
path.pop();
}
}
};