[Algorithm] LeetCode 17. Letter Combinations of a Phone Number in Python

💡 LeetCode 17:

다이얼에서 나올 수 있는 단어 조합 찾기

🌱 코드 in Python

알고리즘: DFS

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        l = len(digits)
        if l == 0:
            return

        ans = []
        words = { "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 dfs(i, s):
            if i == l:
                ans.append(s)
                return
            
            for c in words[digits[i]]:
                dfs(i + 1, s + c)

        dfs(0, "")
        return ans

dfs 문제를 좀 풀어봐야겠단 생각이 들어서 이 문제를 풀어보았다.
그리고 깨달았다. 나는 아직도 dfs 멍청이구나 하는 것을.

아무튼, 일단 숫자에 따른 문자 배열이 필요하다고 생각해서 딕셔너리를 만들어주었다.
그리고 dfs로 순회하며 하나씩 조합을 만들어주었다.

def dfs(i, next_digits):
	if not next_digits:
    	ans.append(s)
    return
            
for c in words[next_digits[0]]:
	dfs(next_digits[1:], s + c)

다른 사람의 풀이를 찾아보니,
이런 식으로 원본 digits 배열을 슬라이싱 해가며 길이가 0이 될 때까지
반복문을 돌리는 방법을 알게 되었다.

그런데 이럴 경우 계속 새 digits 객체가 생성되는 것인데
이게 시간 효율이 더 좋을지는 잘 모르겠다.

마지막으로

chars=[]
for c in digits:
	chars.append(dic[c])
code = product(*chars)
list1 = []
for k in code:
  	list1.append(''.join(k))
return list1

이런 코드도 찾았다.
product는 Itertools 모듈에서 제공하는 함수로
iterable한 객체들의 모든 조합을 반환하는 iterator를 반환한다고 한다.

참 별 게 다 있다 파이썬은

🧠 기억하자

1. dfs.. 잘 하자!
2. *은 언패킹 연산자이다.

LeetCode 17 바로가기