題目出處

17. Letter Combinations of a Phone Number

難度

medium

個人範例程式碼

letter_dict = {
    "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"]
}

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        return self.dfs(digits, [""])

    def dfs(self, digits, combinations):
        # end of recursion
        if not digits:
            return combinations

        # define and split
        new_combinations = []
        for letter in letter_dict[digits[0]]:
            for prefix in combinations:
                new_combinations.append(prefix + letter)

        return self.dfs(digits[1:], new_combinations)

算法說明

還算基礎的 dfs 題目，透過不斷的 dfs，每一次處理掉一個 digits

(除了一開始建那個 table 可能還比較麻煩一些XD)

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

如果沒有 input，return []

Boundary conditions

我們每搜尋一層就減去一個對應的 digit，最後當沒有 digit 時，回傳結果

Reference