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

推荐阅读:
How to use the Leetcode’s Mock Interview Overview to Nail   Replace Harddrives when CrystalDiskInfo Shows Caution Health Sta  Finding the Predecessor and Successor Node of a Binary Search Tr  Algorithms to Detect Pattern of Length M Repeated K or More Time  Using the stdout to debug print the solution in the leetcode con  Tutorial: How to Set Up a API Load Balancer by Using CloudFlare   Introducing the Pancake Sorting Algorithm  What Should You Blog About During the Pandemic and Beyond?  6 Tips For Starting a Business During a Pandemic  Will Your Blog be affected by the Current Facebook Ad Boycott? 
评论列表
添加评论