🎬 Error Handling in Rust Option, Result, the ? operator, and combinators.

📝 Text version (for readers / accessibility)

• Option represents a value that may or may not exist — Some(value) or None

• Result represents success (Ok) or failure (Err) — no exceptions needed

• The ? operator propagates errors up the call stack concisely

• Combinators like .map(), .and_then(), .unwrap_or() chain fallible operations

• The compiler forces you to handle every error case — no silent failures

1067: Phone Keypad Letter Combinations

Difficulty: Intermediate Category: Backtracking Concept: Generate all possible letter combinations from a phone number's digit mapping Key Insight: Each digit expands into 3-4 branches. The iterative queue approach builds combinations level by level; the fold approach is the most concise — each digit transforms all existing prefixes by appending each possible letter.

// 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()
    })
}

fn main() {
    let combos = letter_combos("23");
    println!("Letter combinations of \"23\": {:?}", combos);
}

#[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"

📊 Detailed 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