17. Letter Combination of a Phone Number

Description of the Problem

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 digits 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

Explanation

The core of the solution is to define a function to do Cartesian product for list of string. It can be easily implemented by an nested loop.

Code (Rust)

impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        // m a -> (a -> m b) -> m b
        let product = | v1: &Vec<String>, v2 : &Vec<&str> | -> Vec<String> {
            v1.iter().map(
                |e1| v2.iter().map(
                    |e2| format!("{}{}", e1, e2)
                ).collect::<Vec<String>>()
            )
            .flatten().collect::<Vec<String>>()
        };

        let mut result : Vec<String> = vec![];

        for c in digits.chars() {
            let rhs = match c {
                '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"],
                _ => panic!("Impossible"),
            };

            result = 
                if result.len() == 0 { product(&vec!["".to_string()], &rhs) } 
                else { product(&result, &rhs) };
        }

        return result;
    }
}

Code (Java)

class Solution {
    public List<String> letterCombinations(String digits) {
        if ( digits.equals("") )
            return Collections.emptyList();
        
        List<String> result = List.of("");

        for (char d : digits.toCharArray()){
            switch(d){
                case '2':
                    result = product(result, List.of("a", "b", "c"));
                    break;
                case '3':
                    result = product(result, List.of("d", "e", "f"));
                    break;
                case '4':
                    result = product(result, List.of("g", "h", "i"));
                    break;
                case '5':
                    result = product(result, List.of("j", "k", "l"));
                    break;
                case '6':
                    result = product(result, List.of("m", "n", "o"));
                    break;
                case '7':
                    result = product(result, List.of("p", "q", "r", "s"));
                    break;
                case '8':
                    result = product(result, List.of("t", "u", "v"));
                    break;
                case '9':
                    result = product(result, List.of("w", "x", "y", "z"));
                    break;
            }
        }

        return result;

    }

    List<String> product(List<String> list1, List<String> list2){
        List<String> list3 = new ArrayList<>();
        for(String s1 : list1){
            for(String s2 : list2){
                list3.add(s1+s2);
            }
        }
        return list3;
    }
}

Complexity (d is the length of the digits)

Time complexity:

\(O(4^d)\)
- Each product need len(L_1) * len(L_2)

Auxiliary Space:

\( O(1) \)
- The old List<>/Vec<> is discard in memory by "RAII" if it is not in used.

Leetbook