17、电话号码的字母组合

leetcode

Created At : 2020-07-26 00:19

Count:608 Views 👀 :

Comment:

电话号码的字母组合
1. 示例:
2. 代码

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

示例:

输入：”23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

代码

class Solution {
    String[] chars = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> ans = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return ans;
        int[] nums = new int[digits.length()];
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < nums.length;i++) {
            nums[i] = digits.charAt(i) - '0';
        }
        
        for (int i = 0;i < chars[nums[0]].length();i++) {
            letterCombinationsCore(nums,1,sb.append(chars[nums[0]].charAt(i)));
            sb.delete(sb.length()-1,sb.length());
        }
        
        return ans;
    }
    
    void letterCombinationsCore(int[] nums,int index,StringBuilder pre) {
        // 退出递归
        if (index == nums.length) {
            ans.add(pre.toString());
            return;
        }
        // 递归
        for (int i = 0;i < chars[nums[index]].length();i++) {
            letterCombinationsCore(nums,index + 1,pre.append(chars[nums[index]].charAt(i)));
            pre.delete(pre.length()-1,pre.length());
        }
    }
}


// 用String
class Solution{
    public List<String> letterCombinations(String digits) {

        res = new ArrayList<String>();
        if(digits.equals(""))
            return res;

        findCombination(digits, 0, "");
        return res;
    }

    private void findCombination(String digits, int index, String s){

        if(index == digits.length()){
            res.add(s);
            return;
        }

        Character c = digits.charAt(index);
        String letters = letterMap[c - '0'];
        for(int i = 0 ; i < letters.length() ; i ++){
            // 这里用的是s+xxx,不会改变原来的字符串
            findCombination(digits, index+1, s + letters.charAt(i));
        }

        return;
    }
}


// 官方题解
class Solution {
  Map<String, String> phone = new HashMap<String, 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");
  }};

  List<String> output = new ArrayList<String>();

  public void backtrack(String combination, String next_digits) {
    // if there is no more digits to check
    if (next_digits.length() == 0) {
      // the combination is done
      output.add(combination);
    }
    // if there are still digits to check
    else {
      // iterate over all letters which map 
      // the next available digit
      String digit = next_digits.substring(0, 1);
      String letters = phone.get(digit);
      for (int i = 0; i < letters.length(); i++) {
        String letter = phone.get(digit).substring(i, i + 1);
        // append the current letter to the combination
        // and proceed to the next digits
        backtrack(combination + letter, next_digits.substring(1));
      }
    }
  }

  public List<String> letterCombinations(String digits) {
    if (digits.length() != 0)
      backtrack("", digits);
    return output;
  }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/two-sum/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com