LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，用 dp[i] 表示以 s[i] 结尾的最长有效括号的子串长度

s[i] 必须为右括号才能作为有效括号子串的结尾

如果 s[i - 1] 为左括号
#######() => dp[i] = dp[i - 2] + 2

如果 s[i - 1] 为右括号
#######)) => 找到以 s[i - 1] 为结尾的最长有效括号子串
###@@@@@) => @ 为以 s[i - 1] 为结尾的最长有效括号子串，如果子串前一个符号为左括号则能连上
##(@@@@@) => (@@@@@) 也为有效括号子串 
=> dp[i] = dp[i - 1] + 2 + 以左括号前一个位置为结尾的有效子串长度
=> dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

• 解法如下

class Solution {
 public:
  int longestValidParentheses(string s) {
    int res = 0;
    vector<int> dp(size(s));
    for (int i = 1; i < size(s); ++i) {
      if (s[i] == ')') {
        if (s[i - 1] == '(') {
          if (i == 1) {
            dp[i] = 2;
          } else {
            dp[i] = dp[i - 2] + 2;
          }
        } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
          if (i - dp[i - 1] < 2) {
            dp[i] = dp[i - 1] + 2;
          } else {
            dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
          }
        }
        res = max(res, dp[i]);
      }
    }
    return res;
  }
};