Katkat
Back

Find dictionary words matching a phone digit string

LinkedInSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to map phone keypad digits to characters and efficiently filter a provided dictionary to find words that match a specific digit sequence.

Problem Statement

Given a string of digits digits (where each digit corresponds to a standard phone keypad mapping) and a list of valid words dictionary, return all words from the dictionary that can be formed by the given digit sequence.

Standard phone mapping:

  • 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz

Function Signature

def find_matching_words(digits: str, dictionary: list[str]) -> list[str]:

Constraints

  • digits length: 1 to 10.
  • dictionary size: up to 100,000 words.
  • Each word in the dictionary consists of lowercase English letters.

Examples

Example 1:

  • Input: digits = "23", dictionary = ["ad", "ae", "af", "bd", "cat"]
  • Output: ["ad", "ae", "af"]
  • Explanation: "ad", "ae", and "af" are the only words in the dictionary that can be mapped to "23".

Example 2:

  • Input: digits = "4663", dictionary = ["good", "home", "gone", "food"]
  • Output: ["good", "home"]
  • Explanation: "good" maps to 4663, "home" maps to 4663, "gone" maps to 4663. Wait, "gone" is 4663. All match.

Edge Cases

  • Empty dictionary or empty digits string.
  • No words in the dictionary match the digit sequence.
  • Digit sequence contains '0' or '1', which have no associated letters.

Hints

Hint 1

Pre-process the mapping of digits to characters using a hash map or a fixed-size array.

Hint 2

Filter the dictionary by first checking if a word's length matches the length of the digit string.

Hint 3

For massive dictionaries, consider building a Trie where each node represents a digit, or pre-map all dictionary words into a digit-based hash map.

Follow-up questions

  • How would you optimize the search if you had to perform thousands of queries against the same dictionary?
  • How would you handle dictionary words that contain characters not found on a standard phone keypad (e.g., punctuation)?
  • If the dictionary is too large to fit in memory, what storage or retrieval strategy would you employ?