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?

Answer 1

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

Answer 2

When you say the time complexity of solution is O(N), here N is the length of final string, and definitely not the encoded string.

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?

You analysis is correct. Time Complexity is also a function of the numbers that are represented inside the string and not only dependent on the length of string. So when you are saying the solution is O(N), N is not the length of encoded string, but the length of string upon decoding it.

For eg. Consider the encoded string to be n[an[b]]. Here the output will surely depend on n. If say, n = 3, the output will be abbbabbbabbb. Now, here the length of output is 12. It will not remain static if n changes. So, a rough upper bound function will consist of the numbers inside encoded string as well.

---

So, let's try to deduce a time complexity, let's consider a string -

n1[a[n2[bn3[c...]]]]

In this case, the time complexity is n1*n2*n3...nk which is pretty big and would time-out for large n1,n2...,etc.

For another string say -

n1[a]n2[b]n2[c]

In this case however, the time complexity would be n1+n2+n3, which is linear.

So, the final time-complexity is not truly linear in terms of input size, but will vary depending on input numbers as well. We can consider the upper bound to be

((N11+N12+...+N1k1)*(N21+N22+...+N2k2)*...*(Nn1+Nn2+...+Nnkn)) ,
 
where, Nij = jth number at ith nested level
       k1,k2...kn = number of numbers at 1st,2nd...nth nested level.
       n = number of total nested level

There maybe some tighter bound present. But that's the upper bound I can currently think of right now.

Hope this helps !