LeetCode 17. Letter Combinations of a Phone Numberの解説

#問題概要
2～9の数字を含む文字列が与えられたとき、その数字が表す可能性のあるすべての文字の組み合わせを返せ。答えを任意の順序で返せ。

数字と文字の対応表（電話のボタンと同じ）を以下に示す。1はどの文字にも対応しないことに注意。

例えば"23"という入力に対しては'2'に対しては'a','b','c'が、'3'に対しては'd','e','f'がそれそれひとつずつ割り当てられることになる。'2'が'a'を、'3'が'd'を選ぶと'ad'になる。

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"]

#答え

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:

        phone = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []
        
        if not digits:
            return []
        
        def backtrack(combination, next_digits):
            if not next_digits:
                res.append(combination)
                return
            
            for letter in phone[next_digits[0]]:
                backtrack(combination + letter, next_digits[1:])
        
        backtrack("", digits)
        return res

注目するのはbacktrack()。再起的に呼び出されている。
combinationは"ad"のような文字列であり、最初は空で渡されbacktrack()が呼び出されるたびに文字を付け足していく。
next_digitsは"23"のような数字であり、呼び出されるごとに減っていき、最終的に空になる。
for文の中ではnext_digitsの最初の数字に当たる文字に対してbacktrack()をそれぞれ呼び出している。

例えば"23"であれば次に呼び出されるのは
backtrack('a', '3')
backtrack('b', '3')
backtrack('c', '3')
になる。

backtrack('a', '3')の次に呼び出されるのは
backtrack('ad', '')
backtrack('ae', '')
backtrack('af', '')

ここから先はnext_digitsが空なのでresにその文字列が追加され、return。

#コード改造

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        phone = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}

        def backtrack(combination, next_digits):
            if not next_digits:
                yield combination
                return

            for letter in phone[next_digits[0]]:
                yield from backtrack(combination + letter, next_digits[1:])

        return list(backtrack("", digits))

グローバル関数resを消去するのと、データ節約にyieldを使う。（再帰関数にはyieldが使いやすい？）

yield combination

でデータを保持し、

yield from backtrack(...)

でデータを統合している。

これでよりbacktrack()が独立しやすくなった。