每日一题-电话号码的字母组合-0717

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路

• 采用DFS算法，不撞南墙不回头，回头的时候记得清除当下的状态（回溯）
• 从开始的数字第一个字符开始，找第二个数字的第一个字符……，最后一个数字的第一个字符，长度=digits.length()，代表一个组合形成
• 最后一个数字的第二个字符，又代表一个组合形成……最后一个数字的最后一个字符，又代表一个组合形成
• 递归开始往回找，找到倒数第二个数字的第二个字符，倒数第一个数字的第一个字符……因为字母都是唯一的，所以不考虑去重问题，直到找出所有组合

代码

class Solution {
    
    public String[] letters = {
    "", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
    
        List<String> res = new LinkedList<>();
        if(digits == null || digits.length() == 0)
            return res;
        recur(digits, 0, res, new StringBuilder());
        return res;
    }
    private void recur(String digits, int index, List<String> res, StringBuilder sb){
    
        if(sb.length() == digits.length()){
    
            res.add(sb.toString());
            return;
        }
        // 当前的字符减去0，获取在字符串数组中对应的下标
        int i = digits.charAt(index) - '0';
        String str = letters[i];
        for(int j = 0; j < str.length(); j ++){
    
            sb.append(str.charAt(j));
            recur(digits, index + 1, res, sb);
            sb.deleteCharAt(sb.length() - 1); //将刚拼接好的字符删除
        }

    }
}

进一步思考

如果在“23”组合下，需要达到「ad, ae, af, be, bf, cf」这样的效果，可以改变一下递归的方式，如下

package 回溯;

import java.util.LinkedList;
import java.util.List;

public class test {
    
    public static void main(String[] args){
    
        String digits = "23";
        test sol = new test();
        System.out.println(sol.letterCombinations(digits));
    }
    /** * * @param digits * @return */
    public String[] letters = {
    "", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
    
        List<String> res = new LinkedList<>();
        if(digits == null || digits.length() == 0)
            return res;
        recur(digits,0, 0, res, new StringBuilder());
        return res;
    }
    private void recur(String digits, int cur, int index, List<String> res, StringBuilder sb){
    
        if(sb.length() == digits.length()){
    
            res.add(sb.toString());
            return;
        }
        int j = digits.charAt(cur) - '0';
        String str = letters[j];
        for(int i = index; i < str.length(); i ++){
    
            sb.append(str.charAt(i));
            recur(digits, cur + 1, i, res, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}