17. Letter Combinations of a Phone Number

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

Recursive Solution:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        d=["#","#","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        def getCombo(digits):
            res = []
            if len(digits) == 0:
                return [""]
            nxt= getCombo(digits[1:])
            for curr in nxt:
                for ch in d[int(digits[0])]:
                    res.append(ch+curr)
            return res
        return getCombo(digits)
        

Iterative Solution:

O(N^3)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        d=["#","#","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        res= [""]
        for digit in digits:
            word = d[int(digit)]
            tmp = []
            for curr in res:
                for ch in word:
                    tmp.append(curr+ch)
            res = tmp
        return res
                
        

FIFO Queue Approach (instead of creating tmp arr, treat it as queue)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        d=["#","#","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        res= [""]
        for i,digit in enumerate(digits):
            word = d[int(digit)]
            while len(res[0]) == i:
                curr = res.pop(0)
                for ch in word:
                    res.append(curr+ch)
        return res