public class Solution {
  private static final String[] map = new String[10];
  static {
    map[2] = "abc";
    map[3] = "def";
    map[4] = "ghi";
    map[5] = "jkl";
    map[6] = "mno";
    map[7] = "pqrs";
    map[8] = "tuv";
    map[9] = "wxyz";
  }

  public List<String> letterCombinations(String digits) {
    for (int i = 0; i < digits.length(); i++) {
      if (digits.charAt(i) < '2' || digits.charAt(i) > '9') {
        return new ArrayList<String>();
      }
    }
    return permutations(digits);
  }

  private List<String> permutations(String digits) {
    List<String> all = new ArrayList<String>();
    if (digits.length() == 1) {
      String letters = map[digits.charAt(0) - '0'];
      for (int i = 0; i < letters.length(); i++) {
        all.add("" + letters.charAt(i));
      }
    } else if (digits.length() > 1) {
      List<String> tmp = letterCombinations(digits.substring(1));
      String letters = map[digits.charAt(0) - '0'];
      for (int i = 0; i < letters.length(); i++) {
        for (String str : tmp) {
          all.add("" + letters.charAt(i) + str);
        }
      }
    }
    return all;
  }
}

@@ -1129,8 +1129,1180 @@
 ;%0A  %7D%0A%7D%0A
+%0A// Can also be solved like this:%0A// Time complexity is O(4%5EN), where N is the length of %22digits%22.%0A// Space complexity is O(4%5EN), where N is the length of %22digits%22.%0Aclass Solution %7B%0A  public List%3CString%3E letterCombinations(String digits) %7B%0A    List%3CString%3E res = new ArrayList%3CString%3E();%0A    if (digits.length() == 0) return res;%0A%0A    res.add(%22%22);%0A    for (int i = 0; i %3C digits.length(); i++) %7B%0A      char d = digits.charAt(i);%0A      List%3CString%3E tmp = new ArrayList%3CString%3E();%0A      for (String s : res) %7B%0A        for (String a : letters(d)) %7B%0A          tmp.add(s + a);%0A        %7D%0A      %7D%0A      res = tmp;%0A    %7D%0A    return res;%0A  %7D%0A%0A  private String%5B%5D letters(char digit) %7B%0A    switch (digit) %7B%0A      case '2': return new String%5B%5D%7B%22a%22, %22b%22, %22c%22%7D;%0A      case '3': return new String%5B%5D%7B%22d%22, %22e%22, %22f%22%7D;%0A      case '4': return new String%5B%5D%7B%22g%22, %22h%22, %22i%22%7D;%0A      case '5': return new String%5B%5D%7B%22j%22, %22k%22, %22l%22%7D;%0A      case '6': return new String%5B%5D%7B%22m%22, %22n%22, %22o%22%7D;%0A      case '7': return new String%5B%5D%7B%22p%22, %22q%22, %22r%22, %22s%22%7D;%0A      case '8': return new String%5B%5D%7B%22t%22, %22u%22, %22v%22%7D;%0A      case '9': return new String%5B%5D%7B%22w%22, %22x%22, %22y%22, %22z%22%7D;%0A      default: return new String%5B%5D%7B%7D;%0A    %7D%0A  %7D%0A%7D%0A

update solution