Share my solution with o(n) time and constant space, which is better than DP or using stack.


  • 0
    J

    I think my solution is better than DP or stack because it uses constant space.

    public int longestValidParentheses(String s) {
            if (s == null)
                return 0;
            int max = 0, numOfLeftBracket = 0, tempMax = 0, tempStart = -1;
            boolean isLast=false;
            for (int i = 0; i <= s.length(); i++) {
                char ch = i==s.length()?')':s.charAt(i);
                isLast=i==s.length()?true:false;
                if (ch == '(') {
                    if (tempStart == -1) {
                        tempStart = i;
                    }
                    numOfLeftBracket++;
                    continue;
                }
                if (numOfLeftBracket == 0||isLast) {
                    if (tempMax == 0)
                        continue;
                        /*now we have interval (tempStart, i), which "has" valid parentheses as tempMax, but need to be validated from tail to head by checking ")" */
                    int end = i==s.length()?s.length()-1:i;
                    int numofRightBrackets = 0, temMax2 = 0,temMax3=0;
                    while (end >= tempStart-1) {
                        char cha = end == tempStart-1?'(':s.charAt(end);
                        if (cha == ')') {
                            numofRightBrackets++;
                        } else {
                            if (numofRightBrackets == 0||end==tempStart-1){
                                temMax3=Math.max(temMax3,temMax2);
                                temMax2=0;
                            }else{
                                numofRightBrackets--;
                                temMax2++;
                            }
                        }
                        end--;
                    }
                    max = Math.max(max,temMax3);
                    tempMax = 0;
                    tempStart=-1;
                } else {
                    tempMax++;
                    numOfLeftBracket--;
                }
    
            }
            max = Math.max(max, tempMax);
            return max * 2;
    }

Log in to reply
 

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