17. Letter Combinations of a Phone Number

Problem Statement

link: LeetCode.cn LeetCode 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.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input: ` digits = “” **Output:** []`

Input: digits = "2" Output: ["a","b","c"]

Constraints: 0 <= digits.length <= 4 digits[i] is a digit in the range [‘2’, ‘9’].

Solution Approach

Use a recursive backtracking approach to generate all possible letter combinations for the given digit string by mapping digits to their corresponding letters and combining them systematically.

Algorithm

1. Mapping Digits to Letters: Create a mapping of digits to their corresponding letters based on a phone keypad layout.
2. Recursive Backtracking: Use a recursive function to explore all possible combinations of letters by iterating over the mapped letters for each digit and building combinations step-by-step.
3. Handle Edge Cases: Include a check to return an empty list if the input digit string is empty, ensuring that the function handles cases where no digits are provided.

   Complexity

   time complexity: O(4^n) space complexity: O(4^N)

Implement

    class Solution:
  def letterCombinations(self, digits: str) -> List[str]:
      digits_map = {
          "2":"abc",
          "3":"def",
          "4":"ghi",
          "5":"jkl",
          "6":"mno",
          "7":"pqrs",
          "8":"tuv",
          "9":"wxyz",
      }

      res = []
      n = len(digits)
      if n == 0:
          return []
      def getChar(step, cur): # 0  "a"
          if len(cur) == n:
              res.append(cur)
              return
          letters = digits_map[digits[step]] # map[2]  "abc"
          for c in letters: # abc
              getChar(step + 1, cur + c) # 1 "a"
      getChar(0, "")
      return res

    
    

Twitter  facebook  Email