【Hot100】LeetCode—17. 电话号码的字母组合

---

• 题目连接：17. 电话号码的字母组合

---

1- 思路

String数组（哈希表） + 回溯

思路

• 通过 String 数组实现哈希表，存储 0-9 的哈希表映射

回溯三部曲

• ① 参数及返回值
  • numToStr：String 的哈希表，用来存储 0-9 的映射
  • digits：输入的 字符串，比如 “56”
  • index ：因为需要通过 具体的数字，去 numToStr 中取出映射结果，因此 index 用来记录 digits 遍历到了哪一位
• ② 终止条件
  • index 达到了 digits 的长度
  • 此时收集结果，将 sb.toString 收集到 res 中
• ③ 回溯逻辑
  • 3.1 通过 index 来获取映射的子字符串 str
  • 3.2 通过回溯遍历子字符串 str 收集结果

---

2- 实现

⭐17. 电话号码的字母组合——题解思路

class Solution {List<String> res = new ArrayList<>();public List<String> letterCombinations(String digits) {if(digits.length() == 0 || digits == ""){return res;}String[] numToStr = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};backTracing(digits,numToStr,0);return res;}StringBuilder sb = new StringBuilder();public void backTracing(String digits,String[] numToStr,int index){// 结果收集，终止条件if(digits.length() == index){res.add(sb.toString());return;}// 获取当前映射子串String str = numToStr[digits.charAt(index)-'0'];for(int i = 0 ; i < str.length() ;i++){sb.append(str.charAt(i));backTracing(digits,numToStr,index+1);sb.deleteCharAt(sb.length()-1);}}
}

---

3- ACM 实现

package Daily_LC.Month8_Week4.Day140;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** Solution4** @author alcohol* @Description* @since 2024-08-27 11:35*/
public class Solution4 {static List<String> res = new ArrayList<>();public static List<String> combination(String digits){if(digits.length()==0 || digits==""){return res;}String[] numToStr = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};backTracing(digits,numToStr,0);return res;}static StringBuilder sb = new StringBuilder();public static void backTracing(String digits,String[] numsToString,int index){// 终止条件if(index == digits.length()){res.add(sb.toString());return;}String str = numsToString[digits.charAt(index)-'0'];for(int i = 0 ; i < str.length();i++){sb.append(str.charAt(i));backTracing(digits,numsToString,index+1);sb.deleteCharAt(sb.length()-1);}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();combination(input);System.out.println("结果是"+res.toString());}
}