# Letter Combinations of a Phone Number in Rust

impl Solution {
// Define the function that generates letter combinations from a string of digits.
fn letter_combinations(digits: String) -> Vec<String> {
// Return an empty vector if the input string is empty.
if digits.is_empty() {
return Vec::new();
}

// Create a mapping from each digit to the corresponding letters, using a HashMap.
let phone_map: std::collections::HashMap<char, &str> = [
('2', "abc"),
('3', "def"),
('4', "ghi"),
('5', "jkl"),
('6', "mno"),
('7', "pqrs"),
('8', "tuv"),
('9', "wxyz"),
]
.iter()
.cloned()
.collect();

// Initialize a vector to store the final combinations of letters.
let mut combinations = Vec::new();

// Define the backtrack function, which will be called recursively.
// It takes references to the phone map, the digits string, current index in the digits string,
// a mutable path to store the current combination, and a mutable reference to the combinations vector.
fn backtrack(
phone_map: &std::collections::HashMap<char, &str>,
digits: &str,
index: usize,
path: &mut Vec<char>,
combinations: &mut Vec<String>,
) {
// If the length of the path is equal to the length of the digits string,
// a full combination has been found. Convert path to a String and add it to combinations.
if path.len() == digits.len() {
combinations.push(path.iter().collect());
return;
}

// Get the letters corresponding to the current digit. Use 'nth' to access the digit at the current index.
// The 'unwrap' is safe because we never call this function with an index out of bounds.
if let Some(&letters) = phone_map.get(&digits.chars().nth(index).unwrap()) {
// Iterate over each letter that the current digit maps to.
for letter in letters.chars() {
// Add the letter to the current path.
path.push(letter);
// Recursively call backtrack for the next digit.
backtrack(phone_map, digits, index + 1, path, combinations);
// Remove the last letter to backtrack and try the next letter in the loop.
path.pop();
}
}
}

// Start the backtracking process with the first digit, an empty path, and the combinations vector.
backtrack(&phone_map, &digits, 0, &mut Vec::new(), &mut combinations);

// Return the final combinations.
combinations
}
}