17. Letter Combinations of a Phone Number - python3

4018 ワード

17. Letter Combinations of a Phone Number


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.

My Answer 1: Accepted (Runtime: 28 ms - 82.26% / Memory Usage: 14.3 MB - 27.50%)

from itertools import product
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def switch(ch):
            return {
                '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']
            }.get(ch, -1)
        
        if digits == "":
            return []
        
        if len(digits) == 1:
            return switch(digits)
        
        letter = []
        for ch in digits:
            letter.append(switch(ch))
        
        combinations = list(product(*letter))
        
        result = []
        for i in combinations:
            convertstr = ""
            for j in range(0, len(digits)):
                convertstr += i[j]
            if convertstr != "":
                result.append(convertstr)
        
        return result
Pythonにはswitch文がないので関数にします.
各数値に対応する文字のリストを返します.
itertools import productを使うとリストの組み合わせが得られるので便利です.^^
リストの組合せを持つ組合せをstr組合せに変換してresultに入れて、車に戻って終わりました!
詳細については、Pythonでリスト内のすべての値を取得する組合せを参照してください:https://ourcstory.tistory.com/414
プロダクト関数を除いて、直接実現したいなら遡及を使うべきですが・・・my trauma.....
46.大会と78.Subsetsを参考にしてみたいのですが….私にとってイヴァンセワ...

Approach 1: Backtracking


Solution 1: Runtime: 32 ms - 56.43% / Memory Usage: 14.2 MB - 77.05%

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: 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(combination, next_digits):
            # if there is no more digits to check
            if len(next_digits) == 0:
                # the combination is done
                output.append(combination)
            # if there are still digits to check
            else:
                # iterate over all letters which map 
                # the next available digit
                for letter in phone[next_digits[0]]:
                    # append the current letter to the combination
                    # and proceed to the next digits
                    backtrack(combination + letter, next_digits[1:])
                    
        output = []
        if digits:
            backtrack("", digits)
        return output
丸暗記