[LeetCode][Python3] 17. Letter Combinations of a Phone Number

Problem :

https://leetcode.com/problems/letter-combinations-of-a-phone-number

My Solution :

class Solution:

def letterCombinations(self, digits):

"""

:type digits: str

:rtype: List[str]

"""

self.ans = []

self.conv = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',

'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}

self.combine('', digits)

return self.ans

def combine(self, prefix, remain):

if remain:

for c in self.conv[remain[0]]:

self.combine(prefix + c, remain[1:])

elif prefix:

self.ans.append(prefix)

Comment :

뒤로 갈 수록 경우의 수가 많아지는 문제라서 직관적으로 recursion으로 접근하였다.