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.

Solution: Counting

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minAddToMakeValid(string S) {

int l = 0;

int m = 0;

for (char c : S) {

if (c == '(') ++l;

if (c == ')' && l > 0) {

--l;

++m;

}

return S.size() - m * 2;

}

};

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution: Stack

Using a stack to track the existing open parentheses, if the current one is a close parenthesis but does not match the top of the stack, return false, otherwise pop the stack. Check whether the stack is empty in the end.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isValid(string s) {

map<char, char> p{{')', '('}, {']', '['}, {'}', '{'}};

stack<char> st;

for (char c : s) {

if (!p.count(c)) {

st.push(c);

} else {

if (st.empty() || p[c] != st.top()) return false;

st.pop();

}

return st.empty();

}

};

Python3

# Author: Huahua

class Solution:

def isValid(self, s):

p = {')' : '(', ']': '[', '}' : '{'}

stack = []

for c in s:

if c not in p:

stack.append(c)

else:

if not stack or stack[-1] != p[c]: return False

stack.pop()

return not stack

Posts tagged as “parentheses”

花花酱 LeetCode 921. Minimum Add to Make Parentheses Valid

Solution: Counting

C++

花花酱 LeetCode 20. Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems