【LeetCode】No.17. Letter Combinations of a Phone Number -- Java Version

题目链接： https://leetcode.com/problems/letter-combinations-of-a-phone-number/

1. 题目介绍（电话号码的字母组合）

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

【Translate】： 给定一个包含数字2-9(包括2-9)的字符串，返回该数字可能表示的所有字母组合。以任意顺序返回答案。

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

【Translate】： 下面给出了数字到字母的映射(就像电话按钮一样)。注意，1不映射到任何字母。

【测试用例】：

【约束】：

2. 题解 2.1 双for循环向旧列表中添加新字母 – O(n²)

  annafan的题解，目前在Java Most Vote中排名第一。核心方法combine是使用双for循环向旧列表中添加新字母。

// for example:
gave digits = "23"
i=0 -> result=combine("abc", [""]) ---> [a,b,c];
i=1 -> result=combine("def", [a,b,c]) ---> [ad,bd,cd, ae,be,ce, af,bf,cf];

  public class Solution {
        public static List<String> letterCombinations(String digits) {
            String digitletter[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
            List<String> result = new ArrayList<String>();
    
            if (digits.length()==0) return result;
            
            result.add("");
            for (int i=0; i<digits.length(); i++) 
                result = combine(digitletter[digits.charAt(i)-'0'],result);
            
            return result;
        }
        
        public static List<String> combine(String digit, List<String> l) {
            List<String> result = new ArrayList<String>();
            
            for (int i=0; i<digit.length(); i++) 
                for (String x : l) 
                    result.add(x+digit.charAt(i));
    
            return result;
        }
    }

2.2 Recursive DFS

  sgallivan的题解。

class Solution {
    final char[][] L = {{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},
	{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
    
    public List<String> letterCombinations(String D) {
        int len = D.length();
        List<String> ans = new ArrayList<>();
        if (len == 0) return ans;
        dfs(0, len, new StringBuilder(), ans, D);
        return ans;
    }
    
    public void dfs(int pos, int len, StringBuilder sb, List<String> ans, String D) {
        if (pos == len) ans.add(sb.toString());
        else {
            char[] letters = L[Character.getNumericValue(D.charAt(pos))];
            for (int i = 0; i < letters.length; i++)
                dfs(pos+1, len, new StringBuilder(sb).append(letters[i]), ans, D);
        }
    }
}

2.3 Backtracking

  pedroli97的题解，该方法和2.1很类似。

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return new ArrayList<>();
        
        String[] dict = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        List<String> combos = new ArrayList<>();
        backtrack(combos, digits.toCharArray(), "", dict);
        return combos;
    }
    
    public void backtrack(List<String> combos, char[] digits, String s, String[] dict) {
        if (s.length() == digits.length) { combos.add(s); return; }
        int i = s.length();
        int digit = digits[i] - '0';
        for (char letter : dict[digit].toCharArray()) {
            backtrack(combos, digits, s + Character.toString(letter), dict);
        }
    }
}

2.4 Backtracking & Iterative

  NarutoBaryonMode的题解。

    private static final Map<Character, List<Character>> digitMap = Map.of(
			'0', List.of(), 
			'1', List.of(), 
			'2', List.of('a', 'b', 'c'), 
			'3', List.of('d', 'e', 'f'), 
			'4', List.of('g', 'h', 'i'), 
			'5', List.of('j', 'k', 'l'), 
			'6', List.of('m', 'n', 'o'), 
			'7', List.of('p', 'q', 'r', 's'), 
			'8', List.of('t', 'u', 'v'), 
			'9', List.of('w', 'x', 'y', 'z')
	);

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }

        letterCombinationsHelper(digits, result, new StringBuilder());
        return result;
    }

    private void letterCombinationsHelper(String digits, List<String> result, StringBuilder sb) {
        int len = sb.length();
        if (len == digits.length()) {
            result.add(sb.toString());
            return;
        }

        for (char c : digitMap.get(digits.charAt(len))) {
            sb.append(c);
            letterCombinationsHelper(digits, result, sb);
            sb.setLength(len);
        }
    }