LeetCode 32. Longest Valid Parentheses

Longest Valid Parentheses.

I solve this problem by using DP.

Define DP[i] to be the length of the longest valid parentheses string ended at position i.

If s[i] is a left parenthesis, obvious DP[i] = 0;
If s[i] is a right parenthesis, assume DP[i-1] = x, then if s[i-x-1] is a left parenthesis, DP[i] = DP[i-1] + 2 + DP[i-x-2], else DP[i] = 0.

public class Solution {
    public int LongestValidParentheses(string s) {
        int[] l = new int[s.Length];
        int max = 0;
        for(int i = 0; i < s.Length; i++){ if (s[i] == '(') l[i] = 0; else { if(i == 1 && s[i-1] == '(') { max = 2; l[i] = 2; } if(i == 0) { l[i] = 0; } if(i > 1) {
                    int j = i - l[i-1] - 1;
                    if (j >= 0 && s[j] == '('){
                        l[i] = i - j + 1;
                        if(j > 0) l[i] = l[i] + l[j-1];
                        if(l[i] > max) max = l[i];
                    }
                }
            }
        }
        return max;
    }
}
Tagged

Leave a Reply

Your email address will not be published. Required fields are marked *