[Letcode] [python] Letter Combinations of a Phone Number/전화 번호의 알파벳 조합

제목의 대의.

핸드폰 키보드의 숫자를 입력하고 가능한 모든 자모를 조합하세요.

문제풀이의 방향

DFS 깊이 우선

코드

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        def dfs(num, string, res):
            print string, res
            if num == length:
                res.append(string)
                return
            for letter in dict[digits[num]]:
                print letter
                dfs(num+1, string+letter, res)

        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']
                }
        res = []
        length = len(digits)
        if length == 0:
            return []
        dfs(0, '', res)
        return res

총결산

이 문제의 꼬리표는 회소법 회소법은 시행착오의 사상을 채택하여 단계별로 문제를 해결하려고 시도한다는 것이다.단계별로 문제를 해결하는 과정에서 기존의 단계별 답안이 효과적인 정확한 해답을 얻지 못한다는 것을 시도를 통해 발견할 때, 단계별, 심지어 단계별 계산을 취소하고, 다른 가능한 단계별 해답을 통해 다시 한 번 문제의 해답을 찾으려고 시도한다.
소급법은 일반적으로 가장 간단한 귀속 방법으로 실현하는데 상술한 절차를 반복한 후에 두 가지 상황이 나타날 수 있다.

있을 수 있는 정답을 찾습니다

가능한 모든 단계별 방법을 시도한 후 이 문제에 답이 없음

최악의 경우 회소법은 지수 시간의 계산을 복잡하게 만들 수 있다.