【Leetcode】python – [17] Letter Combinations of a Phone Number 個人解法筆記

➣ Reading Time: 4 minutes

題目出處

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

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 728

1 則留言

★留個言吧!內容有誤或想要補充也歡迎與我討論!