leetcode-backtracking

17. Letter Combinations of a Phone Number.py

class Solution:
    """
    Thought Process:
        we need variable called cur_digit_idx to tell us which level we're in the recursion tree during backtracking.
    
    Time complexity analysis:
        we're going to have n depth of recursion tree. And, for each node we might have 3 choices or 4 choices to go deeper. So, running time would be O(3**m * 4**k), where m+k=n and n = len(input), m is number of digits that map to 3 letters and k is number of digits that map to 4 letters. 
        
    Test case
         digits = "2"
              []
             / | \
            a  b  c
                   i
         digits = "23"
              []
            i=0 / | \
            a  b  c 
         i=1 / | \
        ad  ae af
    """
    def letterCombinations(self, digits: str) -> List[str]:
        """
        T: (3**M * 4** N), where M is number of choices which is 3 and N is # of choices which is 4.
        """
        n = len(digits)
        # edge case
        if n == 0:
            return []
        
        mapping_d_to_s = {'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 = []
        def bactrack(idx_digit = 0, combination = ""):
            if idx_digit == n:
                ans.append(combination)
                return 
            
            for letter in mapping_d_to_s[digits[idx_digit]]:
                bactrack(idx_digit+1, combination + letter)
                
        bactrack()
        return ans
    
    def letterCombinations(self, digits: str) -> List[str]:
        """
        T: O(3^m*4*k), where m+k=n
        S: If we don't count ans array that we store our result, it would be O(n) since we use extra space of combination and recursion stack which is O(n).
        """
        n = len(digits)
        if n==0:
            return []
        
        d_to_letter = {
            '2': 'abc', 
            '3': 'def', 
            '4': 'ghi',
            '5': 'jkl', 
            '6': 'mno', 
            '7': 'pqrs', 
            '8': 'tuv',
            '9': 'wxyz',
        }
        def backtrack(cur_digit_idx, combination=""):
            if cur_digit_idx == n:
                ans.append(combination)
                return # terminate search
            
            cur_digit = digits[cur_digit_idx] # string
            for letter in d_to_letter[cur_digit]:
                backtrack(cur_digit_idx+1, combination+letter)
        
        ans = []
        backtrack(0,"")
        return ans