【LeetCode with Python】 17. Letter Combinations of a Phone Number

题目

原题页面:https://leetcode.com/problems/letter-combinations-of-a-phone-number/
本文地址:http://leetcode.xnerv.wang/letter-combinations-of-a-phone-number/
题目类型:Backtracking, String
难度评价:Medium
类似题目:(M) Generate Parentheses, (M) Combination Sum

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.
200px-Telephone-keypad2

Input: Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.


分析

原题标注类型递归回溯,可能是希望用递归回溯来解决这个问题。但其实这是个尾递归,所以可以直接用循环代替。


代码

class Solution:
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        map = {
               "0":  (),
               "1":  (),
               "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")
               }
        result1 = [ "" ]
        result2 = [ ]
        for ch in digits:
            list = map[ch]
            if 0 == len(list):
                continue
            for str in result1:
                for suffix in list:
                    result2.append(str + suffix)
            result1 = result2
            result2 = [ ]
        return result1

results matching ""

    No results matching ""