c++ - leetcode 394 的时间复杂度

Question

我在 leetcode 上尝试这个问题 https://leetcode.com/problems/decode-string/

我遇到了这个特别的 solution .代码如下。

class Solution {
public:
    string decodeString(string s) {
        stack<string> chars;
        stack<int> nums;
        string res;
        int num = 0;
        for(char c : s) {
            if(isdigit(c)) {
                num = num*10 + (c-'0');                              
            }
            else if(isalpha(c)) {
                res.push_back(c);                
            }
            else if(c == '[') {
                chars.push(res);
                nums.push(num);
                res = "";
                num = 0;
            }
            else if(c == ']') {
                string tmp = res;
                for(int i = 0; i < nums.top()-1; ++i) {
                    res += tmp;
                }
                res = chars.top() + res;
                chars.pop(); nums.pop();
            }
        }
        return res;
     }
};

此解决方案的时间复杂度是否取决于字符串中存在的数字？因为我们多次添加一个字符串。我也觉得是否会进行某种乘法运算。例如

对于输入:3[ab4[c]]

以一种非常粗略的方式，复杂度不会像 3*(len(ab) + 4*(len(c)) 那样。我说得对吗？

Answer 1

我想，虽然不太确定，但您说得有点对。这可能会被认为是 O(N)，因为这些系数不会有太大影响。

只是另一个版本:

#include <string>

class Solution {
public:
    std::string decodeString(const std::string &base_string, int &index) {
        std::string decoded;

        while (index < base_string.length() && base_string[index] != ']') {
            if (!std::isdigit(base_string[index])) {
                decoded += base_string[index++];

            } else {
                int full_num = 0;

                while (index < base_string.length() && std::isdigit(base_string[index])) {
                    full_num = full_num * 10 + base_string[index++] - 48;
                }

                index++;
                std::string character = decodeString(base_string, index);
                index++;

                while (full_num-- > 0) {
                    decoded += character;
                }
            }
        }

        return decoded;
    }

    std::string decodeString(std::string s) {
        int index = 0;
        return decodeString(s, index);
    }
};

---

引用资料

• 有关其他详细信息，您可以查看 Discussion Board .有很多公认的解决方案、解释和各种有效算法 languages ，以及其中的渐近时间/空间复杂度分析。

Image Courtesy