Time complexity of leetcode 394

Question

I was trying this problem on leetcode https://leetcode.com/problems/decode-string/

I came across this particular solution. Code is below.

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

Isn't the time complexity of this solution dependent on the numbers that are present in the string? As we are adding a string that many times. Also I feel if there will be some kind of multiplication going on. For example

For input : 3[ab4[c]]

In a very crude way won't the complexity be something like 3*(len(ab) + 4*(len(c)). Am I correct?

Time complexity is more about operations than actual time. Besides, measuring the size of the output isn't all that useful if any correct algorithm has to produce that output. — Kenny Ostrom

Emma Emma · Accepted Answer · 2020-07-02T17:58:12

I guess, not so sure though, you're somewhat right. That would probably be considered O(N) though since those coefficients would not have much influence.

Just another version:

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

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions, explanations, efficient algorithms with a variety of languages, and asymptotic time/space complexity analysis in there.

Image Courtesy

Time complexity of leetcode 394

2 Answers

References