这个函数检查有效括号的时间复杂度和 Space 复杂度是多少？

Question

我找不到代码的时间复杂度和 Space 复杂度来检查括号是否有效。有人可以帮忙吗？

代码-

bool isValid(string s) 
{
        int s_size = s.length();
        for (int i = 0; i < s_size-1;i++)
        {
            if((s[i]=='(' && s[i+1]==')') || (s[i]=='[' && s[i+1]==']')|| (s[i]=='{' && s[i+1]=='}'))
            {
                s.erase(i, 2);
                i=-1;
                s_size-=2;
            }

        }
        if(s.empty())
            return true;
        else 
            return false;
                
    }

我认为space复杂度是O(1)，时间复杂度是O(n)。如果我错了，请指正。

Answer 1

对于您上面发布的代码片段，时间复杂度为 O(n³)。

正如 n. 'pronouns' m. 正确指出的那样，外部 for 循环 for (int i = 0; i < s_size-1;i++) 运行s n² 次，因为 i 重置每次找到匹配项时都返回起点。而 s.erase() 函数也需要 O(n) 时间到运行。总共弥补了三次 O(n³) 时间复杂度。

您可以阅读 std::string.erase() 函数 here

关于 space 复杂性，您是对的。它的 O(1).

为了有效地解决上述有效括号的问题，即在O(n)时间复杂度和O(n)space复杂度内，考虑使用堆栈。

这个函数检查有效括号的时间复杂度和 Space 复杂度是多少？

What's the Time Complexity and Space Complexity this function to check valid parenthesis?

c++

algorithm

time-complexity

space-complexity