Algorithm to Count the Minimum Add to Make Parentheses Valid

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

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) —

推荐阅读:
小石城山记原文及翻译  钴鉧潭西小丘记原文及翻译  答苏武书原文及翻译  景帝令二千石修职诏原文及翻译  文帝议佐百姓诏原文及翻译  高帝求贤诏原文及翻译  报任少卿书/报任安书原文及翻译  太史公自序原文及翻译  货殖列传序原文及翻译  当生命离开我的时候作文800字 
评论列表
添加评论