Katkat
Back

Generate Every Letter String a Phone Keypad Digit Sequence Can Spell

HeadwaySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given a string of digits from 2 to 9, return every letter string those digits can spell on a standard phone keypad, in lexicographic order. It tests systematic enumeration of combinations, keys that carry four letters, and producing a deterministic output order.

On a standard telephone keypad, each of the digits 2 through 9 carries a set of letters:

DigitLetters
2a b c
3d e f
4g h i
5j k l
6m n o
7p q r s
8t u v
9w x y z

Given a string of digits, return every letter string that the digits can spell, choosing one letter from the key of each digit.

The interview asked a variation of this keypad task; the variation itself was not described, so this console poses the base task.

Function Signature

def keypad_letter_strings(digits: str) -> list[str]:

Rules

  • Every output string has the same length as digits, and its i-th letter is one of the letters on the key of digits[i].
  • Return every such string exactly once.
  • Return the strings in ascending lexicographic order.

Constraints

  • 1 <= len(digits) <= 8
  • Every character of digits is one of 2, 3, 4, 5, 6, 7, 8, 9
  • The output therefore has at most 4^8 = 65,536 strings, each of length at most 8

Examples

Example 1

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

Key 2 offers a, b, c and key 3 offers d, e, f, giving 3 × 3 = 9 strings.

Example 2

Input: digits = "7"
Output: ["p", "q", "r", "s"]

Example 3

Input: digits = "92"
Output: ["wa", "wb", "wc", "xa", "xb", "xc", "ya", "yb", "yc", "za", "zb", "zc"]

Key 9 has four letters, so there are 4 × 3 = 12 strings, listed in lexicographic order.