Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
921. Minimum Add to Make Parentheses Valid.go
921. Minimum Add to Make Parentheses Valid_test.go
README.md

README.md

921. Minimum Add to Make Parentheses Valid

题目

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:

  1. S.length <= 1000
  2. S only consists of '(' and ')' characters.

题目大意

给一个括号的字符串,如果能在这个括号字符串中的任意位置添加括号,问能使得这串字符串都能完美匹配的最少添加数是多少。

解题思路

这题也是栈的题目,利用栈进行括号匹配。最后栈里剩下几个括号,就是最少需要添加的数目。

You can’t perform that action at this time.