P151 电话号码对应的字母组合

描述#

这个题目说的是，给你一个只包含数字 2 ~ 9 的字符串，你要返回它对应的所有字母组合。

数字与字母的映射关系和九宫格键盘上的一样，映射关系如下：
2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz
比如说，给你的数字字符串是 "23"，你要返回的字母组合是：
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
其中，字母组合之间的顺序并不重要，以什么顺序返回都可以。

代码#

public class AlgoCasts {

  private final String[] mapping = new String[]{
    "abc", "def", "ghi", "jkl",
    "mno", "pqrs", "tuv", "wxyz"
  };

  private void combinations(String digits, int idx,
                            String str, List<String> result) {
    if (idx == digits.length()) {
      result.add(str);
      return;
    }
    String chars = mapping[digits.charAt(idx) - '2'];
    for (int i = 0; i < chars.length(); ++i) {
      combinations(digits, idx + 1, str + chars.charAt(i), result);
    }
  }

  // Time: O(4^n), Space: O(n)
  public List<String> letterCombinationsRecursive(String digits) {
    if (digits == null || digits.length() == 0) return Collections.emptyList();
    List<String> result = new ArrayList<>();
    combinations(digits, 0, "", result);
    return result;
  }

  // Time: O(4^n), Space: O(4^n)
  public List<String> letterCombinationsIterative(String digits) {
    if (digits == null || digits.length() == 0) return Collections.emptyList();
    LinkedList<String> result = new LinkedList<>();
    result.add("");
    for (int i = 0; i < digits.length(); ++i) {
      String chars = mapping[digits.charAt(i) - '2'];
      int size = result.size();
      for (int j = 0; j < size; ++j) {
        String str = result.poll();
        for (int k = 0; k < chars.length(); ++k) {
          result.add(str + chars.charAt(k));
        }
      }
    }
    return result;
  }

}