17. Letter Combinations of a Phone Number

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