Problem

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.

Example

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.

Solution

impl Solution {      
    pub fn combinations(mut chars: Vec<char>, index: &std::collections::HashMap<char, Vec<char>>) -> Vec<String> {
        if chars.len() == 0 {
            return vec![];
        }

        let ref char = chars.pop().unwrap();
        let sub_index = index.get(char).unwrap();

        let mut res = Vec::new();

        for r in sub_index {
            let sub = Solution::combinations(chars.clone(), &index);

            if sub.len() == 0 {
                let mut tmp = String::new();
                tmp.push(r.clone());
                res.push(tmp);
            } else {
                for mut sub_v in sub {
                    sub_v.push(r.clone());
                    res.push(sub_v);
                }
            }
        }

        res

    }


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

        let v: Vec<char> = digits.chars().collect();

        return Solution::combinations(v.clone(), &index);
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接