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

• 记录要消除的左右括号数，依次消除每个位置的括号，直到无需消除

class Solution {
 public:
  vector<string> removeInvalidParentheses(string s) {
    vector<string> res;
    int left_parenthese = 0;
    int right_parenthese = 0;
    for (auto& x : s) {
      if (x == '(') {
        ++left_parenthese;
      } else if (x == ')') {
        if (left_parenthese > 0) {
          --left_parenthese;
        } else {
          ++right_parenthese;
        }
      }
    }
    dfs(res, s, 0, left_parenthese, right_parenthese);
    return res;
  }

  void dfs(vector<string>& res, string_view s, int n, int l, int r) {
    if (!l && !r) {
      if (isValid(s)) {
        res.emplace_back(s);
      }
      return;
    }
    for (int i = n; i < size(s); ++i) {
      if (i > n && s[i] == s[i - 1]) {
        continue;  // 避免生成重复结果
      }
      if (l && s[i] == '(') {  // 消除当前位置的左括号
        dfs(res, string{s.substr(0, i)} + string{s.substr(i + 1)}, i, l - 1, r);
      } else if (r && s[i] == ')') {  // 消除当前位置的右括号
        dfs(res, string{s.substr(0, i)} + string{s.substr(i + 1)}, i, l, r - 1);
      }
    }
  }

  bool isValid(string_view s) {
    int cnt = 0;
    for (auto& x : s) {
      if (x == '(') {
        ++cnt;
      } else if (x == ')') {
        --cnt;
      }
      if (cnt < 0) {
        return false;
      }
    }
    return !cnt;
  }
};