n0017_letter_combinations_of_a_phone_number.rs

/**
 * [17] Letter Combinations of a Phone Number
 *
 * Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
 * 
 * A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
 * 
 * <img src="http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png" />
 * 
 * Example:
 * 
 * 
 * Input: "23"
 * Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * 
 * 
 * Note:
 * 
 * Although the above answer is in lexicographical order, your answer could be in any order you want.
 * 
 */
pub struct Solution {}

// submission codes start here

impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        // '0' and '1' as placeholder to avoid index shifting
        let table: Vec<(char, Vec<char>)> = vec![
            ('0', vec![]),
            ('1', vec![]),                ('2', vec!['a','b','c']), ('3', vec!['d','e','f']),
            ('4', vec!['g','h','i']),     ('5', vec!['j','k','l']), ('6', vec!['m','n','o']),
            ('7', vec!['p','q','r','s']), ('8', vec!['t','u','v']), ('9', vec!['w','x','y','z'])
        ];
        if digits.len() < 1 { return vec![] }
        let mut combs: Vec<String> = vec![String::with_capacity(digits.len())];
        for ch in digits.chars().into_iter() {
            let chs = &table[ch.to_digit(10).unwrap() as usize].1;
            let mut added: Vec<String> = Vec::with_capacity((chs.len() - 1) * combs.len());
            for comb in combs.iter_mut() {
                for (i, &alphabetic) in chs.iter().enumerate() {
                    if i == chs.len() - 1 {
                        comb.push(alphabetic);
                    } else {
                        let mut new_comb = (*comb).clone();
                        new_comb.push(alphabetic);
                        added.push(new_comb);
                    }
                }
            }
            combs.append(&mut added);
        }
        combs
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_17() {
        assert_eq!(Solution::letter_combinations("23".to_string()), ["cf", "af", "bf", "cd", "ce", "ad", "ae", "bd", "be"]);
    }
}