题解 | #最长的括号子串#

唉，心情全无。

难受啊。

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
      int res = 0;
      //  连续括号结束的位置（最后一个非连续括号）
      int start = -1;
      std::stack<int> st;
      
      for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '(') {
          st.push(i);
        } else {
          if (st.empty()) {
            start = i;
          } else {
            st.pop();
            if (!st.empty()) {
              res = std::max(res, i - st.top());
            } else {
              res = std::max(res, i - start);
            }
          }
        }
      }
      
      return res;
    }
};

动态规划转移有点费劲

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
      if (s.empty()) {
        return 0;
      }
      //  dp[i] 代表以下表i为结尾的字符串的最长括号子串
      std::vector<int> dp(s.size(), 0);
      int res = 0;
      
      //  只需要查看右括号，以左括号结尾的字符串一定不会是子串
      for (int i = 1; i < s.size(); ++i) {
        if (s[i] == ')') {
          if (s[i - 1] == '(') {
            dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;
            //  找到与之匹配的左括号
          } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
            dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
          }
        }
        res = std::max(res, dp[i]);
      }
      
      return res;
    }
};