欣迪

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'].

這題我用了兩種不同解法。

先講比較容易懂的解法: 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
};

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。