Is there any solution using recursive judgment instead of stack?


  • 0
    S

    I pass 72/73 cases, but can not pass the last case because of "Time limit exceeded", however I try.
    Can you help me to solve that?

    class Solution {
    public:
        bool isValid(string s) {
            unordered_map<char, int> T = { { '(' , 1 },
                                       { ')' , -1 },
                                       { '[' , 2 },
                                       { ']' , -2 },
                                       { '{' , 3 },
                                       { '}' , -3 }};
            if(T[s[0]]<0){
                return false;
            }
            if(s.length()%2==1){
                return false;
            }
            if(s.length()==2&&T[s[0]]>0&&T[s[0]]+T[s[1]]==0){
                return true;
            }
            int tmp=0;
            int cnt=1;
            for(int i=1;i<s.length();i++){
                if(T[s[i]]==T[s[0]]){
                    cnt++;
                }
                if(T[s[i]]==-T[s[0]]){
                    cnt--;
                }
                if(cnt==0){
                    tmp=i;
                    break;
                }
            }
            if(tmp==0||tmp==2){
                return false;
            }
            else if(tmp == 1){
                if (s.length()>tmp+1){
                    return isValid(s.substr(tmp+1));
                }
                else{
                    return true;
                }
                
            }
            
            else{
                if (s.length()>tmp+1){
                    return isValid(s.substr(tmp+1))&&isValid(s.substr(1,tmp-1));
                }
                else{
                    return isValid(s.substr(1,tmp-1));
                }
            }
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.