力扣第17题“电话号码的字母组合”
回溯法(DFS)
回溯法通过递归遍历每个数字对应的字母,生成所有可能的组合。核心思想是构建搜索树,每次选择一个字母后进入下一层递归,回溯时撤销选择以尝试其他分支。
实现步骤:
构建数字到字母的映射表:使用数组或哈希表存储每个数字对应的字母。
递归回溯:
终止条件:当前路径长度等于输入数字字符串长度时,将结果加入列表。
遍历当前数字对应的所有字母,依次选择、递归、撤销选择。
Java代码:
import java.util.*;
//17.电话号码的字母组合
public class LetterCombinations {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String digits = sc.nextLine();
List<String> lists = letterCombinations(digits);
System.out.println(lists);
}
public static List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<String>();
if (digits.length() == 0) {
return combinations;
}
Map<Character, String> phoneMap = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
return combinations;
}
public static void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
if (index == digits.length()) {
combinations.add(combination.toString());
} else {
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {
combination.append(letters.charAt(i));
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.deleteCharAt(index);
}
}
}
}