[leetcode] Longest Valid Parentheses

http://oj.leetcode.com/problems/longest-valid-parentheses/

基本觀察：設isValid(i, j) 表示從i-th到j-th字元中間都是連續的括弧，那麼isValid(i, j)為true有幾種情況

1. 基本情況 長度2：j == i + 1 && str[i] == ‘(‘ && str[j] == ‘)'

2. 遞迴 長度加2：str[i] == ‘(‘ && str[j] == ‘)’ && isValid(i + 1, j - 1)

3. 遞迴 長度加2：str[i] == ‘(‘ && str[j] == ‘)’ && isValid(i -2, j - 2)

一開始用2D DP的方式先把基本情況填完後再填遞迴狀況，但是因為時間複雜度是O(N^2)所以會太慢。後來看了別人的解法知道可以用1D DP的方式解。訣竅是要由後往前填。

1D DP array maxLen[i] 的意義是從i開始往右最長的valid parentheses sequence。

所以由後往前填有兩種情況

1. str[i] == ‘(‘ && str[i + 1] == ‘)’  // 左括弧 右括弧 別的sequence
   如果maxLen[i + 2] > 0的話，可以和str[i: i+1]這對接在一起
2. str[i] == ‘(‘ && maxLen[i + 1] > 0 && str[i + maxLen[i + 1] + 1] == ‘)’  // 左括弧 別的sequence 右括弧
   如果maxLen[i + maxLen[i + 1] + 2] > 0的話，可以和str[i: i + maxLen[i + 1] + 1]這串接在一起