17 Letter Combinations of a Phone Number

Given a digit string, 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.

Input:
Digit string "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.

The Idea: First map each digit to its cooresponding alphabet. Begin with the characters to the first digit.

e.g. if d = 2
s = {"a", "b", "c"}

Next, recursively build upon this string by copying each s[i] and appending each character cooresponding to the next digit.

prev = {"a", "b", "c"}
         |
next = {"ad", "ae", "af"}


prev = {"a", "b", "c"}
              |
next = {"bd", "be", "bf"}


prev = {"a", "b", "c"}
                   |
next = {"cd", "ce", "cf"}

Complexity: O(4^n) time and O(4^n) space

const unordered_map<char, string> num_char =
    { { '2',"abc" },{ '3',"def" },
    { '4',"ghi" },{ '5',"jkl" },
    { '6',"mno" },{ '7',"pqrs" },
    { '8',"tuv" },{ '9',"wxyz" } };

void _letterCombinations(const string &digits, int iter, vector<string> &prev) {
    if (iter < digits.size()) {

        vector<string> next;
        const string target = num_char.at(digits[iter]);
        next.reserve(prev.size() * target.size());

        for (int i = 0; i < prev.size(); i++) {
            string build_upon = prev.at(i);
            for (int j = 0; j < target.size(); j++) {
                string next_str = build_upon + target.at(j);
                next.push_back(next_str);
            }
        }

        prev = next;
        _letterCombinations(digits, iter + 1, prev);
    }
}

string filter_digits(const string &digits) {
    string filtered;
    filtered.reserve(digits.size());
    for (char c : digits)
        if (c - '0' > 1)
            filtered.push_back(c);
    return filtered;
}

vector<string> letterCombinations(string digits) {
    digits = filter_digits(digits);
    if (digits.empty()) return vector<string>();

    vector<string> result;
    for (char c : num_char.at(digits[0])) {
        result.push_back(string(1, c));
    }

    _letterCombinations(digits, 1, result);
    return result;
}

Python Solution 1

This is actually a more efficient solution because I rather than completely rewriting over prev in the previous implementation, I pass in the updated seed (which is next), and return it in the end.

class Solution:
    num_char = {'2': "abc", '3': "def", '4': "ghi",
                '5': "jkl", '6': "mno", '7': "pqrs",
                '8': "tuv", '9': "wxyz"}

    def __letter_combinations(self, digits, index, seed):
        """
        :type digits: str
        :type iter int
        :type seed List[str]
        :rtype: void
        """
        if index < len(digits):
            target = self.num_char[digits[index]]
            next = [prev + char for prev in seed for char in target]
            return self.__letter_combinations(digits, index + 1, next)
        else:
            return seed

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        digits = ''.join(digit for digit in digits if int(digit) > 1)
        if not digits:
            return []

        seed = [char for char in self.num_char[digits[0]]]
        return self.__letter_combinations(digits, 1, seed)


#testing
obj = Solution()
result = obj.letterCombinations("239")
print(result)

Python Solution 2

Incrementally build off the base case, and just keep adding to it.

num_char = {'2': "abc", '3': "def", '4': "ghi",
            '5': "jkl", '6': "mno", '7': "pqrs",
            '8': "tuv", '9': "wxyz"}

class Solution:
    def _letterCombinations(self, current, digit):
        new_current = []
        for comb in current:
            for char in num_char[digit]:
                new_current.append(comb+char)
        return new_current


    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        if not digits: return []
        current = [char for char in num_char[digits[0]]]
        if len(digits) == 1: return current

        for digit in digits[1:]:
            current = self._letterCombinations(current, digit)

        return current