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. Return the answer in any order.

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 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Rust Solution

struct Solution;

use std::collections::HashMap;

impl Solution {
    fn dfs(
        hm: &HashMap<char, Vec<char>>,
        digits: &[char],
        s: &mut Vec<char>,
        res: &mut Vec<String>,
        index: usize,
    ) {
        if index == digits.len() {
            res.push(s.iter().collect());
        } else {
            let d = digits[index];
            for &c in hm[&d].iter() {
                s.push(c);
                Self::dfs(hm, digits, s, res, index + 1);
                s.pop();
            }
        }
    }
    fn letter_combinations(digits: String) -> Vec<String> {
        if digits.is_empty() {
            return vec![];
        }
        let digits: Vec<char> = digits.chars().collect();
        let hm: HashMap<char, Vec<char>> = [
            ('2', "abc"),
            ('3', "def"),
            ('4', "ghi"),
            ('5', "jkl"),
            ('6', "mno"),
            ('7', "pqrs"),
            ('8', "tuv"),
            ('9', "wxyz"),
        ]
        .iter()
        .map(|(d, v)| (*d, v.chars().collect()))
        .collect();
        let mut s: Vec<char> = vec![];
        let mut res: Vec<String> = vec![];
        Self::dfs(&hm, &digits, &mut s, &mut res, 0);
        res
    }
}

#[test]
fn test() {
    let digits = "23".to_string();
    let res: Vec<String> = vec_string!["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"];
    assert_eq!(Solution::letter_combinations(digits), res);
}

Having problems with this solution? Click here to submit an issue on github.