T9 Contact Search
01 · Problem
Old phones let you search contacts by pressing keypad digits, where each digit stands for a group of letters:
2: abc,3: def,4: ghi,5: jkl6: mno,7: pqrs,8: tuv,9: wxyz
You are given an array of distinct lowercase contacts and a string digits made of characters 2-9. Convert each contact name to its digit sequence using the keypad above. Return every contact whose digit sequence starts with digits, sorted in ascending lexicographic order. Return an empty list if none match.
02 · Examples
contacts = ["john","kate","joe","lily","jim"], digits = "56"
["joe","john"]
"john" encodes to 5646 and "joe" to 563, both starting with 56. "kate" (5283), "lily" (5459) and "jim" (546) do not.
contacts = ["amy","bob","cat"], digits = "9"
[]
None of the names start with w, x, y or z.
contacts = ["anna","bob","cody"], digits = "262"
["bob"]
"bob" encodes to 262. "anna" is 2662 and "cody" is 2639, so they do not start with 262.
03 · Constraints
- 011 <= contacts.length <= 104
- 021 <= contacts[i].length <= 20
- 03contacts[i] consists of lowercase English letters; all contacts are distinct
- 041 <= digits.length <= 20
- 05digits consists of characters '2' through '9'
04 · Optimal complexity
- Time
- O(n * L + m log m)
- Space
- O(n * L)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.