Leetcode # 17. Letter Combinations of a Phone Number

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

Solution

n = len(digits)

Time Complexity: O(4 * (4 ** 2) * (4 ** 3) * … * (4 ** n)) = O((4 ** n) * n)
Space Complexity: O(n) (n is also the depth of recursion call stack)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def letterCombinations(self, digits: str) -> List[str]:
    self.comb = {
       "": [], 
      "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"]
    }
    if digits not in self.comb:
      self.comb[digits] = [c1 + c2 \
                           for c1 in self.letterCombinations(digits[:-1]) \
                           for c2 in self.letterCombinations(digits[-1])]
    return self.comb[digits]

Last Updated on 2023/08/16 by A1go