recursion for combinations
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
lookup,result=["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"],[]
self.combinationRecu(result,digits,lookup,"",0)
return result
def combinationRecu(self,result,digits,lookup,cur,n):
if n==len(digits):
result.append(cur)
else:
for choice in lookup[int(digits[n])]:
self.combinationRecu(result,digits,lookup,cur+choice,n+1)
iterative method
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
lookup,result=["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"],[""]
for digit in digits:
choices=lookup[int(digit)]
m,n=len(choices),len(result)
result*=m
for i in xrange(m*n):
result[i]+=choices[i/n]
return result
