Question 1:
Given a string s that only includes' (',' ',' {','} ',' [','] ', judge whether the string is valid.
Valid strings must meet:
- The left parenthesis must be closed with the same type of right parenthesis.
- The left parentheses must be closed in the correct order.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "() [] {}"
Output: true
Example 3:
Input: s = "(]" Output: false
Example 4:
Input: s = "([)]" Output: false
Example 5:
Input: s = "{[]}"
Output: true
Tips:
- 1 <= s.length <= 104
- s consists only of parentheses' () [] {} '
1 class Solution { 2 public boolean isValid(String s) { 3 Stack<Character> stack=new Stack<>(); 4 for (int i=0;i<s.length();i++){ 5 char t=s.charAt(i); 6 if (t=='('||t=='['||t=='{') stack.push(t); 7 else { 8 if (stack.isEmpty()) return false; 9 if (t==')'&&stack.peek()!='(') return false; 10 if (t==']'&&stack.peek()!='[') return false; 11 if (t=='}'&&stack.peek()!='{') return false; 12 stack.pop(); 13 continue; 14 } 15 } 16 if (stack.isEmpty()) return true; 17 else return false; 18 } 19 }
The general idea of bracket title is to judge the pairs of brackets with the stack, press the stack with the left bracket, and let the left bracket out of the stack if the right bracket meets the conditions, otherwise it will be illegal.
Question 2:
Given a string S consisting of '(' and ')' parentheses, we need to add the least parentheses ('(' or ')', which can be anywhere) to make the resulting parenthesis string valid.
Formally, the parenthesized string is valid only if one of the following points is satisfied:
- It is an empty string, or
- It can be written as ， AB (A ， connected with ， B ， where ， A ， and ， B ， are valid strings, or
- It can be written as (A), where ￠ is A valid string.
Given a parenthesis string, returns the minimum number of parentheses that must be added for the result string to be valid.
Example 1:
Input: ()) Output: 1
Example 2:
Input: () Output: 3
Example 3:
Input: () Output: 0
Example 4:
Input: "()" Output: 4
Tips:
- S.length <= 1000
- S ， only contains' ('and') 'characters.
1 class Solution { 2 public int minAddToMakeValid(String s) { 3 Stack<Character> stack=new Stack<>(); 4 int ans=0; 5 for (int i=0;i<s.length();i++) { 6 if (s.charAt(i)=='(') stack.push(s.charAt(i)); 7 else { 8 if (stack.isEmpty()) ans++; 9 else stack.pop(); 10 } 11 } 12 return ans+stack.size(); 13 } 14 }
Similarly, using the stack, when the requirements are not met, the number of parentheses + 1. Note that the last stack may not be empty, and the remaining number of left parentheses needs to be added.
You can also record directly with left without using the stack.
1 class Solution { 2 public int minAddToMakeValid(String s) { 3 int left=0,ans=0; 4 for (int i=0;i<s.length();i++) { 5 if (s.charAt(i)=='(') left++; 6 else { 7 if (left==0) ans++; 8 else left--; 9 } 10 } 11 return ans+left; 12 } 13 }
Question 3:
1541. Minimum number of inserts of balanced bracket stringlabuladong problem solutionthinking
Give you a parenthesized string, s, which contains only the characters' ('and') '. A parenthesized string is called balanced when it satisfies:
- Any left parenthesis' ('must correspond to two consecutive right parentheses')'.
- The left parenthesis' ('must precede the corresponding two consecutive right parentheses')'.
For example, "())", "()) (())" and "(()) ())" are balanced, and "() ()", "())" and "(())" are unbalanced.
You can insert the characters' ('and') 'anywhere to balance the string.
Please return the minimum number of inserts to make {s} balance.
Example 1:
Input: s = "(())" Output: 1 Explanation: the second left parenthesis has two matching right parentheses, but the first left parenthesis has only one right parenthesis. We need to add an extra ')' at the end of the string to make the string into a balanced string "(())".
Example 2:
Input: s = "())" Output: 0 Explanation: the string has been balanced.
Example 3:
Input: s = "()"
Output: 3
Explanation: Add '(' to match the first ')', and then add ')' to match the last '('.
Example 4:
Input: s = "("
Output: 12
Explanation: add 12 ')' to get the balanced string.
Example 5:
Input: s = ")"
Output: 5
Explanation: add 4 '(' at the beginning and 1 ')' at the end of the string, and the string becomes a balanced string "((())".
Tips:
- 1 <= s.length <= 10^5
- s. contains only '(' and ')'.
1 class Solution { 2 public int minInsertions(String s) { 3 int need=0,ans=0; 4 for (int i=0;i<s.length();i++){ 5 if (s.charAt(i)=='(') { 6 need+=2; 7 if (need%2==1){ 8 ans++; 9 need--; 10 } 11 } 12 else { 13 need--; 14 if (need==-1){ 15 ans++; 16 need=1; 17 } 18 } 19 } 20 return ans+need; 21 } 22 }
Idea: maintain the number of right parentheses with need. When the current character is an open parenthesis, the right parenthesis need is increased by 2. If need is an odd number, a right parenthesis needs to be added, that is, res + +, need --. Similarly, if it is a right parenthesis, need --, if need becomes a negative number, it indicates that there are too many right parentheses. At this time, the left parenthesis is added, and the right parenthesis need becomes 1.