6ms simple java DP solution


  • 0
    C
    public class Solution {
        public int longestValidParentheses(String s) {
            if (s == null || s.length() <= 1) return 0;
            int ml = 0;
            int[] good = new int[s.length()];
            for (int i = 1; i < s.length(); ++i) {
                if (s.charAt(i) == ')') {
                    int j = i-1;
                    boolean matched = false;
                    while (j >= 0) {
                        if (s.charAt(j) == '(') {
                            if (matched) break;
                            matched = true;
                            --j;
                        }
                        else {
                            if (good[j] == 0) break;
                            j -= good[j];
                        }
                    }
                    if (matched) {
                        good[i] = i - j;
                        ml = Math.max(ml, good[i]);
                    }
                }
            }
            return ml;
        }
    }

Log in to reply
 

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