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.

• new solution update 2022.02.07

class Solution {
    unordered_map<char, vector<char>> m {
            {'2', {'a','b','c'}},
            {'3', {'d','e','f'}},
            {'4', {'g','h','i'}},
            {'5', {'j','k','l'}},
            {'6', {'m','n','o'}},
            {'7', {'p','q','r','s'}},
            {'8', {'t','u','v'}},
            {'9', {'w','x','y','z'}}
    };
public:
    vector<string> letterCombinations(string digits) {
        if(!digits.length()) return{};
        vector<string> res{""};
        for(auto& c : digits) {
            vector<string> tmp;
            for(auto& ch : m[c]) {
                for(auto& str : res) {
                    tmp.push_back(str + ch);
                }
            }
            swap(tmp,res);
        }
        return res;
    }
};

• back tracking

class Solution {
    unordered_map<char, vector<char>> m {
            {'2', {'a','b','c'}},
            {'3', {'d','e','f'}},
            {'4', {'g','h','i'}},
            {'5', {'j','k','l'}},
            {'6', {'m','n','o'}},
            {'7', {'p','q','r','s'}},
            {'8', {'t','u','v'}},
            {'9', {'w','x','y','z'}}
    };
public:
    vector<string> letterCombinations(string digits) {
        if(!digits.length()) return{};
        vector<string> res{};
        dfs(res, digits, 0, "");
        return res;
    }
    
    void dfs(vector<string>& res, string& d, int i, string ss) {
        if(d.length() == i) {
            res.push_back(ss);
            return;
        }
        for(auto& ch : m[d[i]]) {
            ss.push_back(ch);
            dfs(res, d, i + 1, ss);
            ss.pop_back();
        }
    }
};

class Solution {
private:
    vector<vector<char>> digits = {{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},
                                   {'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
    vector<string> addChar(int digit, vector<string> solution) {
        vector<string> res;
        res.reserve(solution.size() * digits[digit].size());

        for(char alpha : digits[digit]) {
            for(string letter : solution) {
                res.push_back(alpha + letter);
            }
        }

        return res;
    }
public:
    vector<string> letterCombinations(string digits) {
        vector<string> solution;
        if(digits == "")
            return solution;

        solution.push_back("");
        for(int i = digits.length() - 1; i >= 0; i--) {
            solution = addChar(digits[i] & 0b1111, solution);
        }

        return solution;
    }
};