17.Letter Combinations of a Phone Number

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

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 1:

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

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

analyze

方法一: 回溯法递归。

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (digits === '') return []
  const result = []

  combinations(digits, 0, '', result)
  return result
};

/**
 * digits: analyze digit
 * index: current iterator number
 * s: prev total string
 */
var combinations = (digits, index, s, result) => {
  if (index === digits.length) {
    result.push(s)
    return
  }

  const char = digits[index]
  const map = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz'
  }

  const charMapString = map[char]

  for (let i = 0; i < charMapString.length; i++) {
    combinations(digits, index + 1, s + charMapString[i], result)
  }
}

方法二: 运用队列的思想。拿 '23' 举例, 第一轮先放进 'abc', 第二轮分别以队列的方式对 a、b、c 分别进行操作 push 进 def。

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) { // '23'
  const keyString = [
    '',
    '',
    'abc',
    'def',
    'ghi',
    'jkl',
    'mno',
    'pqrs',
    'tuv',
    'wxyz',
  ]

  if (digits === '' || digits.length === 0) {
    return []
  }

  const result = ['']

  for (let x of digits) {
    const size = result.length
    for (let i = 0; i < size; i++) {
      const old = result.shift()

      for (let y of keyString[x]) {
        result.push(old + y)
      }
    }
  }
  return result
};

推荐指数

※※※※※