17. Letter Combinations of a Phone Number

Problem

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.

Solution (Java)

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return Collections.emptyList();
        }
        String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        findCombinations(0, digits, letters, sb, ans);
        return ans;
    }

    private void findCombinations(
            int start, String nums, String[] letters, StringBuilder curr, List<String> ans) {
        if (curr.length() == nums.length()) {
            ans.add(curr.toString());
            return;
        }
        for (int i = start; i < nums.length(); i++) {
            int n = Character.getNumericValue(nums.charAt(i));
            for (int j = 0; j < letters[n].length(); j++) {
                char ch = letters[n].charAt(j);
                curr.append(ch);
                findCombinations(i + 1, nums, letters, curr, ans);
                curr.deleteCharAt(curr.length() - 1);
            }
        }
    }
}

Solution (Javascript)

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (digits.length === 0) return [];
  var res = [''];
  var mapping = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
  bfs(res, 0, digits, mapping, true);
  return res;
};

var bfs = function (res, index, digits, mapping, lead) {
  if (res.length === 0 || index === digits.length) return;
  var tmp = res.pop();
  var chars = mapping[digits[index]];
  bfs(res, index, digits, mapping, false);
  for (var i = 0; i < chars.length; i++) res.push(tmp + chars[i]);
  if (lead) bfs(res, index + 1, digits, mapping, true);
};

Explain:

每一层先把之前的结果一个个出栈，全部出栈后，再把新的推进去，最后由 lead 调用下一层。

Complexity:

• Time complexity :
• Space complexity :