LeetCode題解(0017)：九鍵手機按鍵的字母組合(Python)

題目：原題鏈接（中等）

標籤：字串、回溯演算法

解法	時間複雜度	空間複雜度	執行用時
Ans 1 (Python)	$O(3^N+4^M)$	$O(3^N+4^M)$	32ms (95.50%)
Ans 2 (Python)	$O(3^N+4^M)$	$O(3^N+4^M)$	32ms (95.50%)
Ans 3 (Python)

LeetCode的Python執行用時隨緣，只要時間複雜度沒有明顯差異，執行用時一般都在同一個量級，僅作參考意義。

解法一（列舉法）：

def letterCombinations(self, digits: str) -> List[str]:
    phone = {"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"]}

    ans = [""]
    for d in digits:
        if d in phone:
            new = []
            for item in ans:
                for c in phone[d]:
                    new.append(item + c)
            ans = new

    return ans

解法二（不需要剪枝的回溯演算法）：

測試用例中不包含字元1和字元0

def letterCombinations(self, digits: str) -> List[str]:
    phone = {"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"]}

    def backtrack(now, next_digits):
        if not next_digits:
            ans.append(now)
        else:
            for d in phone[next_digits[0]]:
                backtrack(now + d, next_digits[1:])

    ans = []
    if digits:
        backtrack("", digits)
    return ans