LeetCode - Letter Combinations of a Phone Number

Problem description

description

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

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

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Analysis

This is a standard backtrack problem.

Here’s the code:

public class LetterCombinationsofaPhoneNumber {
  public List<String> letterCombinations(String digits) {
    // miss this edge case
    if (digits.length() == 0){
      return new ArrayList<>();
    }
    HashMap<Character, List<Character>> map = new HashMap<>();

    map.put('2', new ArrayList<>(){{add('a');add('b');add('c');}});
    map.put('3', new ArrayList<>(){{add('d');add('e');add('f');}});
    map.put('4', new ArrayList<>(){{add('g');add('h');add('i');}});
    map.put('5', new ArrayList<>(){{add('j');add('k');add('l');}});
    map.put('6', new ArrayList<>(){{add('m');add('n');add('o');}});
    map.put('7', new ArrayList<>(){{add('p');add('q');add('r');add('s');}});
    map.put('8', new ArrayList<>(){{add('t');add('u');add('v');}});
    map.put('9', new ArrayList<>(){{add('w');add('x');add('y');add('z');}});

    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    backtrack(digits, 0, sb, res, map);
    return res;
  }

  void backtrack(String digits, int index, StringBuilder sb, List<String> res, HashMap<Character, List<Character>> map){
    if (index == digits.length()){
      res.add(sb.toString());
      return;
    }

    char c = digits.charAt(index);
    for(char c1:map.get(c)){
      sb.append(c1);
      backtrack(digits, index+1,sb, res, map);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}

A better solution from LeetCode is not to use backtrack but dfs, reduce the time to delete char at StringBuilder

class Solution {

    public List<String> letterCombinations(String digits) {
        String[] telCharacter = new String[]{" ",
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz"};
        char[] cur = new char[digits.length()];
        List<String> ans = new ArrayList<>();
        dfs(digits, telCharacter, cur, ans,0);
        return ans;
    }

    public void dfs(String digits,String[] telCharacter,char[] cur, List<String> ans,int len) {
        if (len == digits.length()) {
            if(len >0){
                ans.add(new String(cur));
            }
            return;
        }
        String numString = telCharacter[Character.getNumericValue(digits.charAt(len))];
        for(int i=0; i <numString.length();i++) {
            cur[len] = numString.charAt(i);
            dfs(digits, telCharacter, cur, ans, len + 1);
        }
    }
}

use char[] to indicate StringBuilder can improve efficiency. There’s no need to remove here because the len of result is a fixed value so that every path would replace all of the position in the array.

What to improve

• edge case