T9 predictive text generation

If you grew up in the late 90s or early 2000s, you probably remember hammering away at a Nokia or Motorola flip phone, typing messages one digit press at a time. T9, short for "Text on 9 keys," was the predictive text system that made texting bearable before touchscreens took over. Behind that seemingly simple interface was a surprisingly elegant algorithmic challenge: given a sequence of key presses, generate every possible string the user could have intended. This problem, also known as "Letter Combinations of a Phone Number" on other platforms, is a staple at companies like Facebook, LinkedIn, and Twitter because it tests your ability to think recursively about combinatorial problems.

TL;DR

Map each digit (2-9) to its corresponding letters on a phone keypad. Use depth-first search to build every possible string by picking one letter per digit and recursing on the remaining digits. When you have processed all digits, add the completed string to a result set. The time and space complexity are both O(4^n), where n is the number of digits, because the worst-case branching factor is 4 (digits 7 and 9 each map to four letters).

The Problem

90s kids will remember T9, the de-facto cellphone texting technology of the 90s and early 2000s. T9 dialing involves taking a combination of key presses on a classic phone 2-9 keypad and generating all possible strings the user could have intended to enter.

Given a string containing the numbers (2-9) pressed by a user, write a method that returns a set containing all possible strings that can be constructed with the digits. You are provided an existing mapping of digits to possible letters.

Examples:

genT9Strings("3")  -> [d, e, f]
genT9Strings("4")  -> [g, h, i]
genT9Strings("34") -> [dg, dh, di, eg, eh, ei, fg, fh, fi]

Constraints:

• The input string only contains digits 2 through 9
• 0 < len(string) < 10

The Phone Keypad Mapping

Every digit from 2 through 9 maps to a group of letters on the classic phone keypad. Here is the full mapping our solution relies on:

Notice that digits 7 and 9 each map to four letters instead of three. This matters for complexity analysis because the worst case assumes every digit branches four ways.

Why This is a Combinations Problem

At first glance, you might think of this as a permutation problem, but it is actually about combinations drawn from independent sets. For input "23", you pick one letter from {a, b, c} (digit 2) and one letter from {d, e, f} (digit 3). The total number of results is 3 x 3 = 9. More generally, for n digits, you compute the Cartesian product of n letter groups.

The natural way to enumerate a Cartesian product is recursion. Process one digit at a time, choose a letter, and recurse on the remaining digits. When you have chosen a letter for every digit, you have a complete string.

Building the DFS Approach

Let's start with a single digit. If the input is "6", digit 6 maps to {m, n, o}, and the output is simply those three letters:

Now consider two digits, "23". The recursion tree shows every path from root to leaf, and each leaf is a complete output string:

Each level of the tree corresponds to one digit in the input. The first level branches on the letters for digit 2 (a, b, c), and the second level branches on the letters for digit 3 (d, e, f). Every root-to-leaf path produces one output string, giving us 9 results total.

The Recursive Recipe

The DFS helper needs four pieces of information:

1. digits - the original input string
2. index - which digit position we are currently processing
3. stringSoFar - the partial string built from previous digit choices
4. out - the result set that collects completed strings

The base case fires when index equals the length of the digits string, meaning we have chosen a letter for every digit. At that point, stringSoFar is a complete combination and gets added to the output set.

In the recursive case, we look up the letters for digits[index], loop through each letter, append it to stringSoFar, and recurse with index + 1.

Tracing Through the Call Stack

Here is what the first few recursive calls look like for input "23", following the leftmost branch:

The pattern repeats for every branch. After adding "af", the recursion backtracks all the way up to the first level, picks "b" instead of "a", and descends again through "bd", "be", "bf", and so on until all 9 combinations are collected.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
  public Set<String> genT9Strings(String digits) {
    // Create an output set to collect all generated combinations
    Set<String> out = new HashSet<>();
    // Kick off the DFS starting at index 0 with an empty string
    dfsGenerate(digits, 0, "", out);
    return out;
  }

  private void dfsGenerate(String digits, int index, String stringSoFar, Set<String> out) {
    // Base case: all digits processed, add the completed string
    if (index == digits.length()) {
      out.add(stringSoFar);
    } else {
      // Look up the letters for the current digit
      char digit = digits.charAt(index);
      String lettersForDigit = KeyMap.get(digit);
      // Branch on each letter and recurse for the next digit
      for (int i = 0; i < lettersForDigit.length(); i++) {
        dfsGenerate(digits, index + 1, stringSoFar + lettersForDigit.charAt(i), out);
      }
    }
  }

  static final Map<Character, String> KeyMap = Map.of(
    '2', "abc", '3', "def", '4', "ghi", '5', "jkl",
    '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz"
  );
}

Walk through the code with input "23":

1. genT9Strings("23") creates an empty HashSet and calls dfsGenerate("23", 0, "", out).
2. Index 0 corresponds to digit '2', which maps to "abc". The loop iterates through a, b, c.
3. For a, we call dfsGenerate("23", 1, "a", out). Index 1 corresponds to digit '3', mapping to "def".
4. For d, we call dfsGenerate("23", 2, "ad", out). Index 2 equals the string length, so "ad" gets added to the set.
5. Control returns, the loop picks e, producing "ae", then f, producing "af".
6. Back at the first level, the loop moves to b, and the same branching produces "bd", "be", "bf".
7. Finally, c produces "cd", "ce", "cf". The set now holds all 9 combinations.

Complexity Analysis

Time Complexity: O(4^n)

Each digit branches into at most 4 letters (digits 7 and 9). With n digits, the recursion tree has up to 4^n leaf nodes, and building each string takes O(n) character concatenations. The total work is O(n * 4^n), but since n is bounded by the constraint (n < 10), the exponential term dominates, and we write it as O(4^n).

For digits that map to only 3 letters, the actual count is 3^n, but asymptotic analysis uses the worst case.

Space Complexity: O(4^n)

The output set stores up to 4^n strings, each of length n. The recursion call stack adds O(n) frames, but this is dwarfed by the output size. Total space is O(n * 4^n), simplified to O(4^n).

Common Mistakes

1. Forgetting the base case. Without checking index == digits.length(), the recursion never stops and you get a stack overflow.

2. Mutating the partial string. If you use a StringBuilder and forget to remove the last character after the recursive call, subsequent branches will carry stale characters. String concatenation with + avoids this because it creates a new string each time.

3. Hardcoding three letters per digit. Digits 7 and 9 map to four letters. Always use lettersForDigit.length() rather than assuming 3.

4. Using a List when the problem asks for a Set. The problem specifies returning a Set<String>. Using a List would still work here since the mapping produces unique combinations, but matching the return type shows attention to detail.

The Iterative Alternative

You can also solve this without recursion. Start with a list containing just the empty string. For each digit, build a new list by appending every possible letter to every existing string:

public Set<String> genT9StringsIterative(String digits) {
  List<String> current = new ArrayList<>();
  current.add("");

  for (int i = 0; i < digits.length(); i++) {
    String letters = KeyMap.get(digits.charAt(i));
    List<String> next = new ArrayList<>();
    for (String partial : current) {
      for (int j = 0; j < letters.length(); j++) {
        next.add(partial + letters.charAt(j));
      }
    }
    current = next;
  }

  return new HashSet<>(current);
}

This approach has the same O(4^n) complexity but trades recursion stack space for a growing intermediate list. Both are perfectly valid in an interview.

Interview Tips

1. Draw the keypad mapping first. Write out which digits map to which letters. This prevents bugs from misremembering the mapping.

2. Sketch the recursion tree. For input "23", draw the tree showing all 9 paths. This makes the DFS structure obvious and helps you spot the base case.

3. Mention the Trie optimization. If the interviewer asks how to extend this to find real English words, explain that you can filter results against a dictionary. Better yet, use a Trie and prune branches where the current prefix does not exist in the Trie. This is how production T9 implementations actually work.

4. Discuss the iterative alternative. Showing awareness of both approaches demonstrates flexibility and deeper understanding.

5. Clarify edge cases. Ask about empty input (should return an empty set), single-digit input, and whether the output order matters (it does not for a Set).

Key Takeaways

• T9 text generation is a Cartesian product problem: pick one letter from each digit's group and collect every combination.
• DFS with a helper method that tracks the current index and partial string is the cleanest recursive approach.
• The time and space complexity are O(4^n) because digits 7 and 9 branch into 4 letters, and the output must store all combinations.
• String concatenation with + naturally handles backtracking since each recursive call gets its own copy of the string. If you use StringBuilder, remember to undo the append after recursing.
• The iterative approach builds combinations level by level and avoids recursion, but uses the same total memory for the intermediate results.

Solutions in Other Languages

Python

class Solution:
    key_map = {
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"
    }

    def gen_t9_strings(self, digits: str) -> set:
        out = set()
        self.dfs_generate(digits, 0, "", out)
        return out

    def dfs_generate(self, digits, index, string_so_far, out):
        if index == len(digits):
            out.add(string_so_far)
        else:
            digit = digits[index]
            letters_for_digit = self.key_map[digit]
            for i in range(len(letters_for_digit)):
                self.dfs_generate(digits, index + 1, string_so_far + letters_for_digit[i], out)

JavaScript

class Solution {
  constructor() {
    this.KeyMap = new Map([
      ['2', "abc"], ['3', "def"], ['4', "ghi"], ['5', "jkl"],
      ['6', "mno"], ['7', "pqrs"], ['8', "tuv"], ['9', "wxyz"]
    ]);
  }

  genT9Strings(digits) {
    const out = new Set();
    this.dfsGenerate(digits, 0, "", out);
    return out;
  }

  dfsGenerate(digits, index, stringSoFar, out) {
    if (index === digits.length) out.add(stringSoFar);
    else {
      const digit = digits.charAt(index);
      const lettersForDigit = this.KeyMap.get(digit);
      for (let i = 0; i < lettersForDigit.length; i++) {
        this.dfsGenerate(digits, index + 1, stringSoFar + lettersForDigit.charAt(i), out);
      }
    }
  }
}

TypeScript

class Solution {
  private KeyMap: Map<string, string> = new Map([
    ['2', "abc"], ['3', "def"], ['4', "ghi"], ['5', "jkl"],
    ['6', "mno"], ['7', "pqrs"], ['8', "tuv"], ['9', "wxyz"]
  ]);

  genT9Strings(digits: string): Set<string> {
    const out: Set<string> = new Set();
    this.dfsGenerate(digits, 0, "", out);
    return out;
  }

  private dfsGenerate(digits: string, index: number, stringSoFar: string, out: Set<string>): void {
    if (index === digits.length) out.add(stringSoFar);
    else {
      const digit = digits.charAt(index);
      const lettersForDigit = this.KeyMap.get(digit)!;
      for (let i = 0; i < lettersForDigit.length; i++) {
        this.dfsGenerate(digits, index + 1, stringSoFar + lettersForDigit.charAt(i), out);
      }
    }
  }
}

C++

#include <iostream>
#include <string>
#include <map>
#include <unordered_set>

using namespace std;

class Solution {
private:
  map<char, string> KeyMap = {
    {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
    {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
  };

  void dfsGenerate(string digits, int index, string stringSoFar, unordered_set<string>& out) {
    if (index == digits.length()) {
      out.insert(stringSoFar);
    } else {
      char digit = digits[index];
      string lettersForDigit = KeyMap[digit];
      for (int i = 0; i < lettersForDigit.length(); i++) {
        dfsGenerate(digits, index + 1, stringSoFar + lettersForDigit[i], out);
      }
    }
  }

public:
  unordered_set<string> genT9Strings(string digits) {
    unordered_set<string> out;
    dfsGenerate(digits, 0, "", out);
    return out;
  }
};

Scala

import scala.collection.mutable

class Solution {
  def genT9Strings(digits: String): Set[String] = {
    val out: mutable.Set[String] = mutable.Set()
    dfsGenerate(digits, 0, "", out)
    out.toSet
  }

  private def dfsGenerate(digits: String, index: Int, stringSoFar: String, out: mutable.Set[String]): Unit = {
    if (index == digits.length) out.add(stringSoFar)
    else {
      val digit = digits.charAt(index)
      val lettersForDigit = KeyMap(digit)
      for (i <- 0 until lettersForDigit.length) {
        dfsGenerate(digits, index + 1, stringSoFar + lettersForDigit.charAt(i), out)
      }
    }
  }

  val KeyMap: Map[Char, String] = Map(
    '2' -> "abc", '3' -> "def", '4' -> "ghi", '5' -> "jkl",
    '6' -> "mno", '7' -> "pqrs", '8' -> "tuv", '9' -> "wxyz"
  )
}

Kotlin

class Solution {
    fun genT9Strings(digits: String): Set<String> {
        val out = mutableSetOf<String>()
        dfsGenerate(digits, 0, "", out)
        return out
    }

    private fun dfsGenerate(digits: String, index: Int, stringSoFar: String, out: MutableSet<String>) {
        if (index == digits.length) out.add(stringSoFar)
        else {
            val digit = digits[index]
            val lettersForDigit = KeyMap[digit]
            for (i in 0 until lettersForDigit!!.length) {
                dfsGenerate(digits, index + 1, stringSoFar + lettersForDigit[i], out)
            }
        }
    }

    companion object {
        private val KeyMap = mapOf(
            '2' to "abc", '3' to "def", '4' to "ghi", '5' to "jkl",
            '6' to "mno", '7' to "pqrs", '8' to "tuv", '9' to "wxyz"
        )
    }
}

Ruby

require 'set'

class Solution
  KEY_MAP = {
    '2' => 'abc', '3' => 'def', '4' => 'ghi', '5' => 'jkl',
    '6' => 'mno', '7' => 'pqrs', '8' => 'tuv', '9' => 'wxyz'
  }.freeze

  def gen_t9_strings(digits)
    out = Set.new
    dfs_generate(digits, 0, '', out)
    out
  end

  def dfs_generate(digits, index, string_so_far, out)
    if index == digits.length
      out.add(string_so_far)
    else
      digit = digits[index]
      letters_for_digit = KEY_MAP[digit]
      letters_for_digit.each_char do |letter|
        dfs_generate(digits, index + 1, string_so_far + letter, out)
      end
    end
  end
end

Rust

use std::collections::HashSet;

const KEY_MAP: &[(char, &str)] = &[
    ('2', "abc"), ('3', "def"), ('4', "ghi"), ('5', "jkl"),
    ('6', "mno"), ('7', "pqrs"), ('8', "tuv"), ('9', "wxyz"),
];

impl Solution {
    pub fn gen_t9_strings(&self, digits: String) -> HashSet<String> {
        let mut out: HashSet<String> = HashSet::new();
        self.dfs_generate(&digits, 0, String::new(), &mut out);
        out
    }

    fn dfs_generate(&self, digits: &str, index: usize, string_so_far: String, out: &mut HashSet<String>) {
        if index == digits.len() {
            out.insert(string_so_far);
        } else {
            let digit = digits.as_bytes()[index] as char;
            let letters_for_digit = KEY_MAP.iter()
                .find(|&&(d, _)| d == digit)
                .map(|&(_, l)| l)
                .unwrap_or("");
            for ch in letters_for_digit.chars() {
                self.dfs_generate(digits, index + 1, format!("{}{}", string_so_far, ch), out);
            }
        }
    }
}

Swift

class Solution {
    static let keyMap: [Character: String] = [
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    ]

    func genT9Strings(_ digits: String) -> Set<String> {
        var out = Set<String>()
        dfsGenerate(digits, 0, "", &out)
        return out
    }

    private func dfsGenerate(_ digits: String, _ index: Int, _ stringSoFar: String, _ out: inout Set<String>) {
        if index == digits.count {
            out.insert(stringSoFar)
        } else {
            let digit = digits[digits.index(digits.startIndex, offsetBy: index)]
            let lettersForDigit = Solution.keyMap[digit]!
            for letter in lettersForDigit {
                dfsGenerate(digits, index + 1, stringSoFar + String(letter), &out)
            }
        }
    }
}

Dart

class Solution {
  static final Map<String, String> keyMap = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
  };

  Set<String> genT9Strings(String digits) {
    Set<String> out = {};
    _dfsGenerate(digits, 0, "", out);
    return out;
  }

  void _dfsGenerate(String digits, int index, String stringSoFar, Set<String> out) {
    if (index == digits.length) out.add(stringSoFar);
    else {
      String digit = digits[index];
      String lettersForDigit = keyMap[digit]!;
      for (int i = 0; i < lettersForDigit.length; i++) {
        _dfsGenerate(digits, index + 1, stringSoFar + lettersForDigit[i], out);
      }
    }
  }
}

PHP

class Solution {
    private const KEY_MAP = [
        '2' => "abc", '3' => "def", '4' => "ghi", '5' => "jkl",
        '6' => "mno", '7' => "pqrs", '8' => "tuv", '9' => "wxyz"
    ];

    public function genT9Strings(string $digits): array {
        $out = [];
        $this->dfsGenerate($digits, 0, "", $out);
        return $out;
    }

    private function dfsGenerate(string $digits, int $index, string $stringSoFar, array &$out): void {
        if ($index === strlen($digits)) {
            $out[] = $stringSoFar;
            return;
        }
        $lettersForDigit = self::KEY_MAP[$digits[$index]];
        for ($i = 0; $i < strlen($lettersForDigit); $i++) {
            $this->dfsGenerate($digits, $index + 1, $stringSoFar . $lettersForDigit[$i], $out);
        }
    }
}

C#

public class Solution {
    static readonly Dictionary<char, string> KeyMap = new Dictionary<char, string> {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };

    public HashSet<string> GenT9Strings(string digits) {
        var output = new HashSet<string>();
        DfsGenerate(digits, 0, "", output);
        return output;
    }

    private void DfsGenerate(string digits, int index, string stringSoFar, HashSet<string> output) {
        if (index == digits.Length) output.Add(stringSoFar);
        else {
            char digit = digits[index];
            string lettersForDigit = KeyMap[digit];
            for (int i = 0; i < lettersForDigit.Length; i++) {
                DfsGenerate(digits, index + 1, stringSoFar + lettersForDigit[i], output);
            }
        }
    }
}

Practice Makes Perfect

T9 text generation is a great entry point into recursive combination problems. Once you are comfortable with this pattern, try these related challenges:

• Generate Combinations of Parentheses - similar DFS branching with validity constraints
• Recursive String Permutations - rearranging elements from a single set instead of combining from multiple sets
• Phone Keypad Letter Combinations - a close cousin with the same keypad mapping and backtracking structure
• Power Set Exploration - generating all subsets, another classic recursion exercise

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting out or preparing for your dream role at a FAANG company, mastering recursive patterns like this will set you up for success.