Katkat
Back

Solve classic backend coding problems

ChimeBackend Engineer · Technical Screen
MediumBackend EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle string manipulation, recursion with backtracking, and mapping logic by generating all valid word combinations from a numeric keypad sequence.

Problem Statement: Keypad Digit-to-Word Mapping

In older mobile phones, each digit key (2-9) is mapped to a set of letters, similar to the standard T9 keypad. Given a string consisting of digits from '2' through '9', return all possible letter combinations that the number could represent.

Additionally, to ensure the output is meaningful, you are provided with a isValid(word) function (which you can assume exists as an API call) that returns true if a string is a valid word in the English dictionary.

Requirements

Implement the following function: def get_valid_letter_combinations(digits: str) -> List[str]:

  • The mapping of digits to letters follows the standard telephone layout: 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz.
  • Your solution must return a list of valid words that can be formed by the input digit sequence.
  • If the input is empty, return an empty list.

Examples

Example 1: Input: digits = "23" Mapping: 2->abc, 3->def Possible combinations: "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" Output: [list of valid English words from those combinations]

Example 2: Input: digits = "" Output: []

Constraints

  • 0 <= digits.length <= 8
  • The digits map to standard keys.
  • Optimize for time complexity as the depth of the recursion is constrained by the length of the string.

Hints

Hint 1

Use a hash map or an array to store the mapping of digits to their corresponding characters.

Hint 2

Apply a backtracking approach to build the strings character by character, effectively exploring the state space of the keypad.

Hint 3

Prune the search space by integrating the `isValid` check early or using a Trie structure to verify if the prefix being built can lead to a valid word.

Follow-up questions

  • How would your approach change if you were asked to find all valid multi-word phrases for a long sequence of digits, rather than just single words?
  • What is the time complexity of your solution in terms of the number of digits `n` and the average number of letters per digit `k`?
  • If the dictionary is massive, how would you optimize the `isValid` check to reduce latency?