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

目录

• 1- 思路
• • String数组（哈希表） + 回溯
• 2- 实现
• • ⭐17. 电话号码的字母组合——题解思路
• 3- ACM 实现

• 题目连接：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());
    }
}