17. Letter Combinations of a Phone Number

time :

space: O(n)

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;
        
        helper(res, "", digits, 0);
        return res;
    }
    private String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    private void helper(List<String> res, String s, String digits, int index) {
        if (s.length() == digits.length()) {
            res.add(s);
            return;
        }
        String letter = mapping[digits.charAt(index) - '0'];
        for (int i = 0; i < letter.length(); i++) {
            helper(res, s + letter.charAt(i), digits, index + 1);
        }
    }
}

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        
        if (digits == null || "".equals(digits)) return result;
        
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        search("", digits, result, map, 0);
        return result;

    }
    private void search(String s, String digits, List<String> result, Map<Character, String> map, int i) {
        
        //terminator
        if (i == digits.length()) {
            result.add(s);
            return;
        }
        String combinations = map.get(digits.charAt(i)); // get first digits' letters
        
        //process
        for (int j = 0; j < combinations.length(); j++) {
            
            // drill down
            String letter = combinations.substring(j, j+1); //use substring is faster
            search(s + letter, digits, result, map, i+1); // i is recursion level
        }
    }
}

for example

new version

T: O(4^n*n), at most 4 digits, n is digits length, last *n => is String concat..

S: O(2*4 + n), dfs stack is n

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String>  result = new ArrayList<>();
        if ("".equals(digits)) {
            return result;
        }

        Map<Character, List<Character>> map = new HashMap<>();
        map.put('2', Arrays.asList('a', 'b', 'c'));
        map.put('3', Arrays.asList('d', 'e', 'f'));
        map.put('4', Arrays.asList('g', 'h', 'i'));
        map.put('5', Arrays.asList('j', 'k', 'l'));
        map.put('6', Arrays.asList('m', 'n', 'o'));
        map.put('7', Arrays.asList('p', 'q', 'r', 's'));
        map.put('8', Arrays.asList('t', 'u', 'v'));
        map.put('9', Arrays.asList('w', 'x', 'y', 'z'));
        
        dfs(digits, 0, "", map,result);
        return result;
    }
    private void dfs(String digits, int start, String str, Map<Character, List<Character>> map, List<String> result) {
        if (str.length() == digits.length()) {
            result.add(str);
            return;
        }
        char cur = digits.charAt(start);
        for (char c : map.get(cur)) {
            dfs(digits, start+1, str + String.valueOf(c), map, result);
        }
    }
}

/*

23

2 -> abc
3 -> def

  2 a   b    c
  /     |     \ 
def    def    def
*/  

better one I think

T: O(4^n*n), at last concat String with n times , n is digits length

S: O(n), recursion stack

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if ("".equals(digits)) {
            return result;
        }
        String mappings[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        dfs(digits, 0, mappings, result, new StringBuilder()); // sb will do backtracking to original "", so always use same sb
        return result;
    }
    private void dfs(String digits, int start, String mappings[], List<String> result, StringBuilder sb) {
        if (start == digits.length()) {
            result.add(sb.toString());
            return;
        }
        
        String mapping = mappings[digits.charAt(start) - '0'];
        for (char m : mapping.toCharArray()) {
            sb.append(m);
            dfs(digits, start + 1, mappings, result, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

/*
  2 [abc]
  //\
a  b c
3 [def]
/   \    \ backtracking
def  def def -> reach result length add to result(List<String>)


4^4
*/