LeetCode-in-All

17. Letter Combinations of a Phone Number

Medium

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'].

Solution

impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        if digits.is_empty() {
            return vec![];
        }

        let letters = vec![
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        ];

        let mut ans = vec![];
        let mut sb = String::new();
        Solution::find_combinations(0, &digits, &letters, &mut sb, &mut ans);
        ans
    }

    fn find_combinations(
        start: usize,
        digits: &str,
        letters: &[&str],
        curr: &mut String,
        ans: &mut Vec<String>,
    ) {
        if curr.len() == digits.len() {
            ans.push(curr.clone());
            return;
        }

        for i in start..digits.len() {
            let n = digits.chars().nth(i).unwrap().to_digit(10).unwrap() as usize;
            for ch in letters[n].chars() {
                curr.push(ch);
                Solution::find_combinations(i + 1, digits, letters, curr, ans);
                curr.pop();
            }
        }
    }
}

This site is open source. Improve this page.