use std::collections::{HashMap};

impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        if digits.len() == 0 {
            return vec![];
        }
        let mut table = HashMap::new();
        table.insert('2', vec!['a', 'b', 'c']);
        table.insert('3', vec!['d', 'e', 'f']);
        table.insert('4', vec!['g', 'h', 'i']);
        table.insert('5', vec!['j', 'k', 'l']);
        table.insert('6', vec!['m', 'n', 'o']);
        table.insert('7', vec!['p', 'q', 'r', 's']);
        table.insert('8', vec!['t', 'u', 'v']);
        table.insert('9', vec!['w', 'x', 'y', 'z']);

        let mut res = vec![];
        Solution::letter_combinations_0(&table, &digits, 0, &mut "".to_string(), &mut res);
        return res;
    }

    pub fn letter_combinations_0(table: &HashMap<char, Vec<char>>, digits: &String, curi: usize, cur: &mut String, collector: &mut Vec<String>) {
        if cur.len() == digits.len() {
            collector.push(cur.clone());
            return;
        }
        let c = digits.chars().nth(curi).unwrap();
        let x = table.get(&c).unwrap();
        for a in x.iter() {
            cur.push(*a);
            Solution::letter_combinations_0(table, digits, curi + 1, cur, collector);
            cur.pop();
        }
    }
}