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.

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:

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

Solution: Backtracking

Solution: Iterative

We use a vector to store the previous words combination, and a new vector to add new combinations. We can start from the beginning with 0 digit. Then for every new digit, we add each char to the words in previous vector, and push them to the new vector. After each iteration, we update the previous vector.

Time complexity of is O(4^n)

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> table =  {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> ans = {""};

        for (int i = 0; i < digits.size(); i++){
            vector<string> arr;
            string chars = table[digits[i] - '0'];
            for (auto ch: chars) {
                for (auto str: ans) {
                    arr.push_back(str+ch);
                }
            }
            ans = arr;
        }
        return ans;
    }

Solution: Using queue

The idea is to use queue to store previous words. We can tell if the char has been added to the words by checking the size of the word.

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

        vector<string> t = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue<string> q;
        q.push("");

        for (int i=0; i<digits.size(); i++) {
            int d = digits[i] - '0';
            while (q.front().size() == i) {
                string s = q.front();
                q.pop();
                for (auto ch: t[d]) {
                    q.push(s+ch);
                }
            }
        }

        vector<string> ans;
        while (!q.empty()) {
            ans.push_back(q.front());
            q.pop();
        }

        return ans;
    }