Letter combinations of a phone number

Hash Table String Backtracking

65.5% acceptance

Jan 12, 2026

20814

1127

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn letter_combinations(digits: String) -> Vec<String> {
    if digits.is_empty() {
      return vec![];
    }
    
    let mapping = vec![
      "",     // 0
      "",     // 1
      "abc",  // 2
      "def",  // 3
      "ghi",  // 4
      "jkl",  // 5
      "mno",  // 6
      "pqrs", // 7
      "tuv",  // 8
      "wxyz", // 9
    ];
    
    let mut result = Vec::new();
    let mut current = String::new();
    
    Self::backtrack(&digits, 0, &mut current, &mut result, &mapping);
    
    result
  }
  
  fn backtrack(
    digits: &str,
    index: usize,
    current: &mut String,
    result: &mut Vec<String>,
    mapping: &[&str],
  ) {
    if index == digits.len() {
      result.push(current.clone());
      return;
    }
    
    let digit = digits.chars().nth(index).unwrap();
    let digit_num = digit.to_digit(10).unwrap() as usize;
    let letters = mapping[digit_num];
    
    for letter in letters.chars() {
      current.push(letter);
      Self::backtrack(digits, index + 1, current, result, mapping);
      current.pop();
    }
  }
}