leetcode 394的时间复杂度

Question

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

• 有关其他详细信息，请参阅讨论板。这里有许多公认的解决方案、解释、各种语言的高效算法，以及渐近的时间/空间复杂性分析。