leetcode 394 的时间复杂度

Question

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

我遇到了这个特殊的解决方案。代码如下。

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

参考

• 有关其他详细信息，您可以查看讨论板。里面有很多公认的解决方案、解释、多种语言的高效算法，以及渐近的时间/空间复杂度分析。

图片提供