Algorithm to Count the Minimum Add to Make Parentheses Valid

  • 时间:2020-09-24 11:54:15
  • 分类:网络文摘
  • 阅读:76 次

Given a string S of ‘(‘ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(‘ or ‘)’, and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.
  • Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:
Input: “())”
Output: 1

Example 2:
Input: “(((”
Output: 3

Example 3:
Input: “()”
Output: 0

Example 4:
Input: “()))((”
Output: 4

Note:
S.length <= 1000
S only consists of ‘(‘ and ‘)’ characters.

Parentheses Balance Algorithm

The algorithm is to count the number of the left Parentheses and, if we meet right Parentheses, we increment the answer if there is no enough left Parentheses, or we decrement the counter as to close the corresponding left Parentheses.

The final answer (the minimal add) plus the counter of the left Parentheses as we need to add to close them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minAddToMakeValid(string S) {
        int left = 0;
        int ans = 0;
        for (const auto &n: S) {
            if (n == '(') {
                left ++;
            } else {
                if (left > 0) {
                    left --;
                } else {
                    ans ++;
                }
            }
        }
        return ans + left;
    }
};
class Solution {
public:
    int minAddToMakeValid(string S) {
        int left = 0;
        int ans = 0;
        for (const auto &n: S) {
            if (n == '(') {
                left ++;
            } else {
                if (left > 0) {
                    left --;
                } else {
                    ans ++;
                }
            }
        }
        return ans + left;
    }
};

O(N) time as we need to scan the entire string and O(1) space, obviously.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
餐饮020 新开餐厅微信微博营销四段法  如何实现微博的有效营销呢?  微博营销怎么做?看这篇就行了  微博营销如何赚钱?我给大家提供一些思路  百度AI生态的建立 给创业公司带来了什么好处?  创业项目营销效果不佳 只因没做好这几件事  AI把英语系新生吓退学?别急,我们从来都是那只懒蚂蚁  创业初期该做什么?首先你需要避开的这5大坑!  2018世界人工智能大会开幕,它给创业者带来了哪些思路?  创业寒冬下 初创公司如何才可以打破C轮死魔咒? 
评论列表
添加评论