LeetCode T17 - Phone Number

刷LeetCode的时候发现一个道理。用go语言写：“哇塞，我挺厉害的嘛”；用c++写：“哇靠，垃圾程序的典范！😭”

第17题是一个典型选择问题，要求从给定的数字中选择几个需要的字母。解法存在优化，但基本上就是DFS。leetcode 17 题的一个解法如下。

这里是递归的做法，非常好理解：

• base case：如果最后一个数字，则逐一添加每个字母到需要被添加的子串中；
• recurrence case：如果非最后一个，则遍历当前的所有字母，进入下一个循环。

其实，这种类似尾递归的做法，编译器可以优化。但做题的时候，leetcode好像出了问题，不管怎么优化都没法做到0ms。。。

string mapping[8]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
class Solution {
   public:
    Solution() {}
    ~Solution() {}
    vector<string> letterCombinations(string digits) {
        if (digits.length()<=0) return vector<string>{};
        vector<string> m;
        for (char& i : digits) {
            m.push_back(getString(i - '0'));
        }
        solve(m, "", 0, digits.length());
        return this->s;
    }
    void solve(vector<string> &m, string candidate, int ptr, int len) {
        if (ptr == len - 1) {
            for (char& i : m[ptr]) {
                s.push_back(candidate + i);
            }
        } else {
            for (char& i : m[ptr]) {
                solve(m, candidate+i, ptr+1, len);
            }
        }
    }
   private:
    vector<string> s;
    inline string getString(const int a) { return mapping[a - 2]; };

};

递归改迭代：

class Solution {
   public:
    Solution() {}
    ~Solution() {}
    vector<string> letterCombinations(string digits) {
        unordered_map<char, string> mapping{
            {'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};

        if (digits.empty()) return {};
        vector<int> steps{1};
        int sum = 1;
        for (auto& i : digits) {
            sum *= mapping[i].length();
            steps.push_back(sum);
        }
        vector<string> m(sum);
        for (size_t i = 0; i < digits.length(); i++) {
            string& s = mapping[digits[i]];
            int j = 0;
            while (j < sum) {
                for (int k = j; k < j + sum / steps[i + 1]; k++) {
                    m[k] += s[(k / (sum / steps[i + 1])) % s.length()];
                }
                j += sum / steps[i + 1];
            }
        }

        return m;
    }
};