921. Minimum Add to Make Parentheses Valid

由()组成的字符串，问最少添加多少个(或)能使所有()配对。()配对问题和301类似，遇到(+1)-1当值为负时说明(缺，需要res+1，并重置值为0。当最后值为正时说明(多，因为只要返回需要增加的值而不是找具体的位置，无需向301一样再反着遍历一遍，直接让值和res相加即结果。

/*
 * @lc app=leetcode id=921 lang=cpp
 *
 * [921] Minimum Add to Make Parentheses Valid
 */

// @lc code=start
class Solution {
public:
    int minAddToMakeValid(string S) {
        const int N = S.length();
        int res = 0, c = 0;
        for (int i = 0; i < N; ++i) {
            if (S[i] == '(') ++c;
            else --c;
            if (c < 0) {
                ++res;
                ++c;
            }
        }
        return res + c;
    }
};
// @lc code=end

Previous1249. Minimum Remove to Make Valid Parentheses Next678. Valid Parenthesis String

Last updated 5 years ago

Was this helpful?

921. Minimum Add to Make Parentheses Valid

/*
 * @lc app=leetcode id=921 lang=cpp
 *
 * [921] Minimum Add to Make Parentheses Valid
 */

// @lc code=start
class Solution {
public:
    int minAddToMakeValid(string S) {
        const int N = S.length();
        int res = 0, c = 0;
        for (int i = 0; i < N; ++i) {
            if (S[i] == '(') ++c;
            else --c;
            if (c < 0) {
                ++res;
                ++c;
            }
        }
        return res + c;
    }
};
// @lc code=end

Previous1249. Minimum Remove to Make Valid Parentheses Next678. Valid Parenthesis String

Last updated 5 years ago

Was this helpful?