[DFS, 백트래킹] Letter Combinations of a Phone Number

 

Letter Combinations of a Phone Number - LeetCode

내 풀이

from collections import deque
from typing import List
 
def letterCombinations(digits: str) -> List[str]:
    d = dict()
    d['2'] = ['a', 'b', 'c']
    d['3'] = ['d', 'e', 'f']
    d['4'] = ['g', 'h', 'i']
    d['5'] = ['j', 'k', 'l']
    d['6'] = ['m', 'n', 'o']
    d['7'] = ['p', 'q', 'r', 's']
    d['8'] = ['t', 'u', 'v']
    d['9'] = ['w', 'x', 'y', 'z']
 
    # digit = ['2', '3']
    def dfs(digit: deque, temp: list):
        if len(temp) == len(digits):
            ans.append(''.join(temp))
            return
 
        v = digit.popleft()
        for alpha in d[v]:
            temp.append(alpha)
            dfs(digit, temp)  # dfs([3], 'a'], dfs([], 'ad')
            temp.pop()
        return digit.appendleft(v)  # 없으면 ['ad', 'ae', 'af', 'b', 'c']
 
    if digits == '':
        return []
 
    ans = []
    q = deque(digits)
    dfs(q, [])  # dfs([2,3], ' ')
    return ans
 
 
digits = "234"
print(letterCombinations(digits))

다른 풀이

from typing import List
 
def letterCombinations(digits: str) -> List[str]:
    def dfs(index, path):
        # 백트래킹
        if len(path) == len(digits):
            result.append(path)
            return
 
        i = index
        for j in d[digits[i]]:
            dfs(i + 1, path + j)
 
    d = dict()
    d['2'] = ['a', 'b', 'c']
    d['3'] = ['d', 'e', 'f']
    d['4'] = ['g', 'h', 'i']
    d['5'] = ['j', 'k', 'l']
    d['6'] = ['m', 'n', 'o']
    d['7'] = ['p', 'q', 'r', 's']
    d['8'] = ['t', 'u', 'v']
    d['9'] = ['w', 'x', 'y', 'z']
 
    if not digits:
        return []
    result = []
    dfs(0, '')
    return result
 
 
digits = "235"
print(letterCombinations(digits))

---

1.
26번 째 줄 retrun이 없어도 digit에 append된 값이 dfs스택 아래에 쌓인 dfs에서의 digit에서도 적용된다.

2.
dfs(path + j) 방식을 사용하는게  append, pop 보다 깔끔한 코드를 만든다. 
dfs(index, path)는 자주 사용되는 파라미터 값이다.

3.
백트래킹 조건은 웬만하면 함수 최상단에 존재한다.