mercredi 7 avril 2021

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

I am unable to find the Time Complexity and Space Complexity of the code to check valid parenthesis. Can anyone help, please?

code -

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

I think the space complexity is O(1) and the time complexity is O(n). Correct me please, if I am wrong.

Aucun commentaire:

Enregistrer un commentaire