【LeetCode】使括号有效的最少添加

叶茂林

发布于 2024-06-05 13:21:14

700

发布于 2024-06-05 13:21:14

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目链接： 921. 使括号有效的最少添加 - 力扣（LeetCode）

对于一个只有（）组合的括号字符串，如果想要这个字符串是有效的括号对，找出最少需要插入多少个括号

括号离不开栈，栈可以消除有效的括号，先用栈将左括号装起来，遇到右括号并且栈非空就弹栈，如果遇到右括号栈空就计数，说明需要插入左括号，完事之后栈里面的元素就都是左括号，都计数，因为都需要加上右括号

class Solution {
public:
    int minAddToMakeValid(string s) {
        int ans = 0;
        stack<char> match;
        for (auto c : s) {
            if (c == '(')
                match.push(c);
            else if (match.empty())
                ++ans;
            else if (match.top() == '(' && c == ')')
                match.pop();
        }
        return ans + match.size();
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-04，如有侵权请联系 cloudcommunity@tencent.com 删除

int