17. Letter Combinations of a Phone Number

Solution 1: Recursive + DFS

class Solution:
    def dfs(self, digitMap, digits, idx, currCombin, currAns): 
            if idx == len(digits):
                currAns.append(currCombin)
                return
            
            dg = digits[idx]
            for char in digitMap[dg]:
                currCombin += char
                self.dfs(digitMap, digits, idx + 1, currCombin, currAns)
                currCombin = currCombin[:-1]
            return currAns
                
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
            
        digitMap = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z'],
        }
        ans = self.dfs(digitMap, digits, 0, "", [])
        return ans

Time Complexity: O(2^N) // 3-4 symol set * N times
Space Complexity: O(N)

Solution 2: Iterative + BFS

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
            
        dgMap = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]
        ans = []
        ans.append("")
        for dg in digits:
            currCombin = []
            while len(ans):
                prevCombin = ans.pop(0)
                for char in dgMap[ord(dg) - ord('0')]:
                    currCombin.append(prevCombin + char)
            ans = currCombin
        return ans

Time Complexity: O(2^N)
Space Complexity: O(N)

Reference

https://zxi.mytechroad.com/blog/searching/leetcode-17-letter-combinations-of-a-phone-number/

Follow-up: Count Number of Texts