LeetCode 17. [Python] Letter Combinations of a Phone Number
原题链接
中等
作者:
徐辰潇
,
2021-01-20 05:06:45
,
所有人可见
,
阅读 352
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
#TC: O(3**n)
#SC: O(3**n) n = len(digits)
#Typical backtracking method for solving combination problem
Map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
n = len(digits)
res = []
if len(digits) == 0:
return res
def helper(idx, Str):
if idx == n:
res.append(Str)
return
for Char in Map[digits[idx]]:
helper(idx+1, Str+Char)
helper(0, "")
return res