[誤答注]Let Code#17 Letter Combinations of Phone Number

教訓
dfsは難しすぎて...少し熟すようです.

LeetCode問題リンク

出所:朴相吉著,Pythonアルゴリズムインタビュー,p.338

質問する
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.
文字列に2～9の数字が含まれている場合は、その数値で作成できるすべての文字の組合せを返します.順番は関係ありません.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
次の携帯電話のボタンのような画像は、数字対字対応を示しており、1はどの文字にも対応していません.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4

digits[i] is a digit in the range ['2', '9'].

の意見を打診
Solution #1
いずれにしてもdigitsの長さは0,1,2,3,4しかないので,症例ごとに区分すればよいのではないでしょうか.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letter = ['', 
                  '', 'abc', 'def', 
                  'ghi', 'jkl', 'mno', 
                  'pqrs', 'tuv', 'wxyz']
        
        result = []
        
        if len(digits) == 1:
            for c1 in letter[int(digits[0])]:
                result.append(c1)
                
        elif len(digits) == 2:
            for c1 in letter[int(digits[0])]:
                for c2 in letter[int(digits[1])]:
                    result.append(''.join([c1, c2]))
                    
        elif len(digits) == 3:
            for c1 in letter[int(digits[0])]:
                for c2 in letter[int(digits[1])]:
                    for c3 in letter[int(digits[2])]:
                        result.append(''.join([c1, c2, c3]))
                        
        elif len(digits) == 4:
            for c1 in letter[int(digits[0])]:
                for c2 in letter[int(digits[1])]:
                    for c3 in letter[int(digits[2])]:
                        for c4 in letter[int(digits[3])]:
                            result.append(''.join([c1, c2, c3, c4]))

		# len(digits) == 0이라면 그냥 빈 리스트 반환
        return result

通過します.

Success
Runtime: 34 ms, faster than 71.70% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 13.9 MB, less than 91.67% of Python3 online submissions for Letter Combinations of a Phone Number.

しかしもちろん醜い.
少し一般化しているようで、len(digits)によってfor文が重なる個数が異なり、一般化しにくい.
このようなものはどうして一般化できるのか.
Solution #2
一般化がさらに困難になる原因の一つは,文字列のマージに気まずいことである.'ab'に'c'を加えると気まずいです.
しかし、よく考えてみると、Pythonには文字列joinを非常に直感的に行う方法があります.'ab' + 'c' = 'abc'です!
に答える

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            if len(path) == len(digits):
                result.append(path)
                return
            for i in range(index, len(digits)):
                for j in dic[digits[i]]:
                    dfs(i+1, path+j) # path+j는 문자열 join이다!
            
        if not digits:
            return []
        dic = {
                '2': 'abc', 
                '3': 'def',
                '4': 'ghi',
                '5': 'jkl',
                '6': 'mno',
                '7': 'pqrs',
                '8': 'tuv',
                '9': 'wxyz'
            }
        result = []
        dfs(0, '')       
        return result

path情報をdfs上で更新し、一緒に伝達する方法は非常に斬新である.