新年好啊新年好

最近leetcode的c++版本好像有点。。问题？就是，求解之后，特别吃内存。哪怕是他给的程序，复制粘贴提交，还是会非常吃内存。

用c++写几道题就发现，
go语言写：哇塞，程序挺不错的嘛！
c++写：哇靠，垃圾程序的典范！

e.g.: problem 17 phone number，典型的DFS题目。

一开始很快就能想到简单的递归方法：

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]; };

};

结果，4ms，4.7MB 内存。哇靠，垃圾程序的典范！

然后，改成了迭代：

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;
    }
};

时间内存还是没变化。没道理吧。。。
然后我把给的0ms的example复制粘贴提交，发现，不可能达到0ms～2ms之间。不管怎么优化，内存都是4MB以上。

于是乎得出了个结论：leetcode上的c++提交时间判断可能是对的，但内存肯定是错的hhh
折腾了一晚上，无果。