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 <= 4digits[i]is a digit in the range['2', '9'].
這題我用了兩種不同解法。
先講比較容易懂的解法： Array.prototype.reduce()
var letterCombinations = function(digits) {
if (!digits) return []
const btns = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r','s'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
return queries.reduce((arr, key, idx) => {
const newArr = []
const item = btns[key]
if (idx === 0) return item
for (let i = 0; i < arr.length; i++) {
for(let j = 0; j < item.length; j++) {
newArr.push(`${arr[i]}${item[j]}`)
}
}
return newArr
}, null)
};
用 .reduce 方法，比較容易理解。
先排除沒有輸入任何指令的行為：
if (!digits) return []
.reduce
假設輸入是 “12” ，那麼可能的數量就會是 [“a”, “b”, “c”] 和 [“d”, “e”, “f”] 配對，共 9 種。
如果輸入 “123” ， 那麼可能的結果會是 “12” 的結果再和 [“g”, “h”, “i”] 配對，共 27 種。
因此，我們在每一層把結果記錄下來，再不斷遞迴結果，到下一個輸入的按鈕去做配對。
特別注意一點是 reduce 的第二個參數 initialValue ：
於第一次呼叫 callback 時要傳入的累加器初始值。若沒有提供初始值，則原陣列的第一個元素將會被當作初始的累加器。假如於一個空陣列呼叫 reduce() 方法且沒有提供累加器初始值，將會發生錯誤。
這邊帶了 null，目的是為了讓迴圈的 idx 從 0 開始跑，才能將第一次的結果轉換成陣列。
如果設定這個參數，則 idx 會從 1 開始，初始帶入的值會是 queries[0]。
return queries.reduce((arr, key, idx) => {
const newArr = []
const item = btns[key]
if (idx === 0) return item
for (let i = 0; i < arr.length; i++) {
for(let j = 0; j < item.length; j++) {
newArr.push(`${arr[i]}${item[j]}`)
}
}
return newArr
}, null)
理解 reduces 之後，同樣的概念用 for loop 寫出來。
這邊會變成三層迴圈，蠻複雜的。但邏輯是不變的。
做一個 output 的陣列，代替 .reduce 方法中不斷遞迴的結果。
進入第二層邏輯和 .reduce 方法大致相同。
var letterCombinations = function(digits) {
if (!digits) return []
const btns = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r','s'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
const queries = digits.split('')
let output = btns[queries[0]]
for (let i = 1; i < queries.length; i++) {
const arr = []
for(let j = 0; j < output.length; j++) {
for(let k = 0; k < btns[queries[i]].length; k++){
arr.push(output[j] + btns[queries[i]][k])
}
}
output = arr
}
return output
};
