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

/**
 * @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 :