1067 Intermediate

1067-letter-combinations — Phone Keypad Letter Combinations

Functional Programming

Tutorial

The Problem

Given a phone number keypad string (digits 2–9), generate all possible letter combinations. This is a classic Cartesian product problem: each digit maps to a set of letters, and you want all combinations taking one letter from each digit's set.

The problem appears in T9 predictive text input (legacy phones), QR code testing tools that enumerate all encodings, and any system generating all strings from a grammar.

🎯 Learning Outcomes

• Implement Cartesian product via backtracking

• Implement the same via iterative queue-based expansion

• Understand the connection between Cartesian products and nested loops

• Handle edge cases (empty input, single digit)

• Connect to formal language theory: this generates words in a regular language

Code Example

#![allow(clippy::all)]
// 1067: Phone Keypad Letter Combinations

const PHONE_MAP: &[&str] = &[
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
];

// Approach 1: Backtracking
fn letter_combos(digits: &str) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }
    let mut results = Vec::new();
    let mut current = String::new();
    let digits: Vec<usize> = digits.bytes().map(|b| (b - b'0') as usize).collect();

    fn backtrack(idx: usize, digits: &[usize], current: &mut String, results: &mut Vec<String>) {
        if idx == digits.len() {
            results.push(current.clone());
            return;
        }
        for c in PHONE_MAP[digits[idx]].chars() {
            current.push(c);
            backtrack(idx + 1, digits, current, results);
            current.pop();
        }
    }

    backtrack(0, &digits, &mut current, &mut results);
    results
}

// Approach 2: Iterative with queue
fn letter_combos_iter(digits: &str) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }
    let mut queue = vec![String::new()];
    for b in digits.bytes() {
        let letters = PHONE_MAP[(b - b'0') as usize];
        let mut next_queue = Vec::new();
        for current in &queue {
            for c in letters.chars() {
                let mut s = current.clone();
                s.push(c);
                next_queue.push(s);
            }
        }
        queue = next_queue;
    }
    queue
}

// Approach 3: Functional with fold
fn letter_combos_fold(digits: &str) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }
    digits.bytes().fold(vec![String::new()], |acc, b| {
        let letters = PHONE_MAP[(b - b'0') as usize];
        acc.iter()
            .flat_map(|prefix| letters.chars().map(move |c| format!("{}{}", prefix, c)))
            .collect()
    })
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_backtrack() {
        let r = letter_combos("23");
        assert_eq!(r.len(), 9);
        assert!(r.contains(&"ad".to_string()));
        assert!(r.contains(&"cf".to_string()));
    }

    #[test]
    fn test_iter() {
        let r = letter_combos_iter("23");
        assert_eq!(r.len(), 9);
    }

    #[test]
    fn test_fold() {
        let r = letter_combos_fold("23");
        assert_eq!(r.len(), 9);
    }

    #[test]
    fn test_empty() {
        assert!(letter_combos("").is_empty());
    }

    #[test]
    fn test_single() {
        assert_eq!(letter_combos("7").len(), 4); // pqrs
    }
}

(* 1067: Phone Keypad Letter Combinations *)

let phone_map = [|
  "";     (* 0 *)
  "";     (* 1 *)
  "abc";  (* 2 *)
  "def";  (* 3 *)
  "ghi";  (* 4 *)
  "jkl";  (* 5 *)
  "mno";  (* 6 *)
  "pqrs"; (* 7 *)
  "tuv";  (* 8 *)
  "wxyz"; (* 9 *)
|]

(* Approach 1: Backtracking *)
let letter_combos digits =
  if String.length digits = 0 then []
  else begin
    let results = ref [] in
    let buf = Buffer.create (String.length digits) in
    let rec backtrack idx =
      if idx = String.length digits then
        results := Buffer.contents buf :: !results
      else begin
        let letters = phone_map.(Char.code digits.[idx] - Char.code '0') in
        String.iter (fun c ->
          Buffer.add_char buf c;
          backtrack (idx + 1);
          let len = Buffer.length buf in
          Buffer.truncate buf (len - 1)
        ) letters
      end
    in
    backtrack 0;
    List.rev !results
  end

(* Approach 2: Functional with List.concat_map *)
let letter_combos_func digits =
  if String.length digits = 0 then []
  else begin
    let chars_of_string s = List.init (String.length s) (fun i -> s.[i]) in
    let digit_chars idx =
      chars_of_string phone_map.(Char.code digits.[idx] - Char.code '0')
    in
    let rec solve idx =
      if idx = String.length digits then [""]
      else
        let letters = digit_chars idx in
        let rest = solve (idx + 1) in
        List.concat_map (fun c ->
          List.map (fun suffix -> String.make 1 c ^ suffix) rest
        ) letters
    in
    solve 0
  end

(* Approach 3: Iterative with queue *)
let letter_combos_iter digits =
  if String.length digits = 0 then []
  else begin
    let queue = Queue.create () in
    Queue.push "" queue;
    for i = 0 to String.length digits - 1 do
      let letters = phone_map.(Char.code digits.[i] - Char.code '0') in
      let size = Queue.length queue in
      for _ = 1 to size do
        let current = Queue.pop queue in
        String.iter (fun c ->
          Queue.push (current ^ String.make 1 c) queue
        ) letters
      done
    done;
    Queue.fold (fun acc x -> x :: acc) [] queue |> List.rev
  end

let () =
  let r1 = letter_combos "23" in
  assert (List.length r1 = 9);
  assert (List.mem "ad" r1);
  assert (List.mem "cf" r1);

  let r2 = letter_combos_func "23" in
  assert (List.length r2 = 9);

  let r3 = letter_combos_iter "23" in
  assert (List.length r3 = 9);

  assert (letter_combos "" = []);
  assert (List.length (letter_combos "7") = 4);

  Printf.printf "✓ All tests passed\n"

Key Differences

String mutation: Rust uses String::push and String::pop for in-place character manipulation during backtracking; OCaml uses string concatenation.

Iterative expansion: Both iterative versions use a collection that grows by Cartesian product; Rust uses a Vec<String> and extends it explicitly.

**String::pop**: Rust's current.pop() undoes the last push(c) for backtracking; OCaml's immutable string approach naturally supports backtracking.

**PHONE_MAP indexing**: Both use digit-minus-base offset (digit - '0') to index the map — identical arithmetic.

OCaml Approach

let phone_map = [|""; ""; "abc"; "def"; "ghi"; "jkl"; "mno"; "pqrs"; "tuv"; "wxyz"|]

let letter_combos digits =
  if digits = "" then []
  else
    String.fold_left (fun acc d ->
      let letters = phone_map.(Char.code d - Char.code '0') in
      if acc = [] then List.map (String.make 1) (String.to_seq letters |> List.of_seq)
      else List.concat_map (fun combo ->
        List.map (fun c -> combo ^ String.make 1 c)
          (String.to_seq letters |> List.of_seq)
      ) acc
    ) [] (String.to_seq digits |> List.of_seq)

OCaml's List.concat_map provides the Cartesian product expansion cleanly.

Full Source

#![allow(clippy::all)]
// 1067: Phone Keypad Letter Combinations

const PHONE_MAP: &[&str] = &[
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
];

// Approach 1: Backtracking
fn letter_combos(digits: &str) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }
    let mut results = Vec::new();
    let mut current = String::new();
    let digits: Vec<usize> = digits.bytes().map(|b| (b - b'0') as usize).collect();

    fn backtrack(idx: usize, digits: &[usize], current: &mut String, results: &mut Vec<String>) {
        if idx == digits.len() {
            results.push(current.clone());
            return;
        }
        for c in PHONE_MAP[digits[idx]].chars() {
            current.push(c);
            backtrack(idx + 1, digits, current, results);
            current.pop();
        }
    }

    backtrack(0, &digits, &mut current, &mut results);
    results
}

// Approach 2: Iterative with queue
fn letter_combos_iter(digits: &str) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }
    let mut queue = vec![String::new()];
    for b in digits.bytes() {
        let letters = PHONE_MAP[(b - b'0') as usize];
        let mut next_queue = Vec::new();
        for current in &queue {
            for c in letters.chars() {
                let mut s = current.clone();
                s.push(c);
                next_queue.push(s);
            }
        }
        queue = next_queue;
    }
    queue
}

// Approach 3: Functional with fold
fn letter_combos_fold(digits: &str) -> Vec<String> {
    if digits.is_empty() {
        return vec![];
    }
    digits.bytes().fold(vec![String::new()], |acc, b| {
        let letters = PHONE_MAP[(b - b'0') as usize];
        acc.iter()
            .flat_map(|prefix| letters.chars().map(move |c| format!("{}{}", prefix, c)))
            .collect()
    })
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_backtrack() {
        let r = letter_combos("23");
        assert_eq!(r.len(), 9);
        assert!(r.contains(&"ad".to_string()));
        assert!(r.contains(&"cf".to_string()));
    }

    #[test]
    fn test_iter() {
        let r = letter_combos_iter("23");
        assert_eq!(r.len(), 9);
    }

    #[test]
    fn test_fold() {
        let r = letter_combos_fold("23");
        assert_eq!(r.len(), 9);
    }

    #[test]
    fn test_empty() {
        assert!(letter_combos("").is_empty());
    }

    #[test]
    fn test_single() {
        assert_eq!(letter_combos("7").len(), 4); // pqrs
    }
}

(* 1067: Phone Keypad Letter Combinations *)

let phone_map = [|
  "";     (* 0 *)
  "";     (* 1 *)
  "abc";  (* 2 *)
  "def";  (* 3 *)
  "ghi";  (* 4 *)
  "jkl";  (* 5 *)
  "mno";  (* 6 *)
  "pqrs"; (* 7 *)
  "tuv";  (* 8 *)
  "wxyz"; (* 9 *)
|]

(* Approach 1: Backtracking *)
let letter_combos digits =
  if String.length digits = 0 then []
  else begin
    let results = ref [] in
    let buf = Buffer.create (String.length digits) in
    let rec backtrack idx =
      if idx = String.length digits then
        results := Buffer.contents buf :: !results
      else begin
        let letters = phone_map.(Char.code digits.[idx] - Char.code '0') in
        String.iter (fun c ->
          Buffer.add_char buf c;
          backtrack (idx + 1);
          let len = Buffer.length buf in
          Buffer.truncate buf (len - 1)
        ) letters
      end
    in
    backtrack 0;
    List.rev !results
  end

(* Approach 2: Functional with List.concat_map *)
let letter_combos_func digits =
  if String.length digits = 0 then []
  else begin
    let chars_of_string s = List.init (String.length s) (fun i -> s.[i]) in
    let digit_chars idx =
      chars_of_string phone_map.(Char.code digits.[idx] - Char.code '0')
    in
    let rec solve idx =
      if idx = String.length digits then [""]
      else
        let letters = digit_chars idx in
        let rest = solve (idx + 1) in
        List.concat_map (fun c ->
          List.map (fun suffix -> String.make 1 c ^ suffix) rest
        ) letters
    in
    solve 0
  end

(* Approach 3: Iterative with queue *)
let letter_combos_iter digits =
  if String.length digits = 0 then []
  else begin
    let queue = Queue.create () in
    Queue.push "" queue;
    for i = 0 to String.length digits - 1 do
      let letters = phone_map.(Char.code digits.[i] - Char.code '0') in
      let size = Queue.length queue in
      for _ = 1 to size do
        let current = Queue.pop queue in
        String.iter (fun c ->
          Queue.push (current ^ String.make 1 c) queue
        ) letters
      done
    done;
    Queue.fold (fun acc x -> x :: acc) [] queue |> List.rev
  end

let () =
  let r1 = letter_combos "23" in
  assert (List.length r1 = 9);
  assert (List.mem "ad" r1);
  assert (List.mem "cf" r1);

  let r2 = letter_combos_func "23" in
  assert (List.length r2 = 9);

  let r3 = letter_combos_iter "23" in
  assert (List.length r3 = 9);

  assert (letter_combos "" = []);
  assert (List.length (letter_combos "7") = 4);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_backtrack() {
        let r = letter_combos("23");
        assert_eq!(r.len(), 9);
        assert!(r.contains(&"ad".to_string()));
        assert!(r.contains(&"cf".to_string()));
    }

    #[test]
    fn test_iter() {
        let r = letter_combos_iter("23");
        assert_eq!(r.len(), 9);
    }

    #[test]
    fn test_fold() {
        let r = letter_combos_fold("23");
        assert_eq!(r.len(), 9);
    }

    #[test]
    fn test_empty() {
        assert!(letter_combos("").is_empty());
    }

    #[test]
    fn test_single() {
        assert_eq!(letter_combos("7").len(), 4); // pqrs
    }
}

Deep Comparison

Phone Keypad Letter Combinations — Comparison

Core Insight

Each digit maps to 3-4 letters, creating a tree of combinations. Three approaches: backtracking (DFS), iterative queue (BFS-like), and fold (functional). The fold is most elegant, treating each digit as a transformation on the set of prefixes.

OCaml Approach

• Buffer for string building with truncate for backtracking

• String.iter to iterate over digit's letters

• List.concat_map for functional branching

• Queue module for iterative approach

Rust Approach

• String::push/pop for backtracking

• PHONE_MAP as const &[&str] array

• flat_map + format! for fold approach — very expressive

• Vec as queue with swap for iterative approach

Comparison Table

Aspect	OCaml	Rust
Phone map	`let phone_map = [\|...\|]`	`const PHONE_MAP: &[&str]`
Digit to index	`Char.code d - Char.code '0'`	`(b - b'0') as usize`
String backtrack	`Buffer.truncate`	`String::pop()`
Functional	`List.concat_map`	`flat_map` + `format!`
Queue approach	`Queue.t` (mutable)	`Vec` swap per level

Exercises

Extend the keypad map to include * and # symbols and test with phone numbers including these characters.

Generate combinations filtered by a dictionary: return only letter combinations that form valid English words.

Implement letter_combos_lazy(digits: &str) -> impl Iterator<Item=String> that generates combinations lazily without collecting all into a Vec.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust