[Search] LC 17. Letter Combinations of a Phone Number

Goal

• Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
• By taking consideration of the problem constraint, using iterative solution will not pass the tests

Strategy

• Recursive DFS with depth set to the length of the input string, and a counter starts from 1
• Once counter reached the depth, exit recursion, and append to res
• Inside of recursions, simply append each letter, and pass down to the next round

Highlight

• DFS with a counter
• Setting up a depth with the length of the input

Complexity

• Time: O(4^n) when we hit the worst case scenario with all digits falls into the 4 groups
• Time: O(4^n+n) for storing the outputs

Code

class Solution:
   
    def dfs(self, s, i, target,digits):
        if i==target:
            self.res.append(''.join(s))
            return
   
        lst = self.d[digits[i]]
        for char in lst:
            s.append(char)
            self.dfs(s,i+1,target, digits)
            s.pop()
        
            
     
            
    def letterCombinations(self, digits: str) -> List[str]:
        self.d = {'2':'abc',
            '3':'def',
            '4':'ghi',
             '5':'jkl',
            '6':'mno',
            '7':'pqrs','8':'tuv', '9':'wxyz'}
        self.res = []
        if len(digits)==0:
            return []
        self.dfs([],0, len(digits), digits)
        return self.res