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
};

推荐指数

※※※※※