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
    }
}