My 242ms java solution


  • 0
    G

    // The idea is to mark the valid parentheses with boolean array and then count the longest continuous 'true'
    public class Solution {
    public int longestValidParentheses(String s) {
    if(s==null) return 0;
    if(s.length()==0) return 0;

        int count=0;
        int max=0;
        boolean[] visited=new boolean[s.length()]; // use boolean array to mark the valid parentheses
        
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==')'){
                int j=i-1;
                while(j>=0){
                    if(s.charAt(j)=='(' && visited[j]==false){
                        visited[j]=true;
                        visited[i]=true;
                        break;
                    }
                    j--;
                }
            }
        }
        
        // look for the longest valid parentheses length
        for(boolean v:visited){
            if(v==true){
                count++;
            }else{
                if(count>max) max=count;
                count=0;
            }
        }
        
        if(count>max) max=count;
        
        return max;
        
    }
    

    }


  • 0
    H

    What is your time complexity? O(n^2)?


  • 0
    G

    yes, the complexity is O(n^2).


Log in to reply
 

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