当前位置:网站首页>Leetcode32 longest valid bracket (dynamic programming difficult problem)
Leetcode32 longest valid bracket (dynamic programming difficult problem)
2022-07-06 03:59:00 【ajdhfla】
Give you one that only contains '(' and ')' String , Find the longest effective ( The format is correct and continuous ) The length of the bracket substring .
Example 1:
Input :s = "(()"
Output :2
explain : The longest valid bracket substring is "()"
Example 2:
Input :s = ")()())"
Output :4
explain : The longest valid bracket substring is "()()"
Example 3:
Input :s = ""
Output :0
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/longest-valid-parentheses
One : Violence solution ( Easy to understand but with high time complexity )
The easiest way to think about this problem is to find the length of the longest valid bracket substring ending in each character in the string , When I think of this, I think of using dynamic programming , But the state transition equation of this problem is not well determined , I will write the solution of dynamic programming below . The simplest way to find the longest substring ending in each character is to solve it violently through the stack , The specific method is to traverse forward from the current character , Until it doesn't meet the conditions .
Here are a few things to pay attention to :
1. Because this is traversal from back to front , So what is different from usual is that when you encounter the right parenthesis, it will be put on the stack , Stack when encountering the left bracket ;
2. How to determine the conditions for breaking the cycle : When the stack is empty and the next character in the stack is ‘(' when ;
3. In the general question of judging whether it is valid , If the stack is not empty after traversal, it is directly determined that it is invalid , But this problem may happen :"))()", If you traverse forward from the last character , It is partly effective , So how to exclude the invalid part in the front . I set up a temp Variable , Except at the beginning, if the stack is empty, it indicates that there is already a set of valid parentheses , At this point through tmep To record its length . Then continue to traverse forward , Because there may be valid parentheses after it , When the stack is not empty at the end of traversal, it will return directly temp, That is, the previous valid part .
class Solution {
public int longestValidParentheses(String s) {
if (s.length() == 0) return 0;
int ans = 0;
int[] dp = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
}
return ans;
}
public int a (String s, int x) {
Deque<Character> stack = new LinkedList<>();
int res = 0;
int temp = 0;
for (int i = x; i >= 0; --i) {
if (stack.isEmpty() && i != s.length() - 1 && s.charAt(i + 1) == '(') temp = res;
if (stack.isEmpty() && s.charAt(i) == '(') break;
else if (s.charAt(i) == ')') stack.addLast(s.charAt(i));
else if (s.charAt(i) == '(') {
stack.pollLast();
}
res++;
}
if(!stack.isEmpty()) return temp;
return res;
}
}
Two : Dynamic programming
The key of dynamic programming is to determine the state transition equation , The same idea as above requires the length of the longest valid bracket substring ending in each character in the string , And recorded in the array dp[] in , The idea is as follows :
Traversal string
1. If the current character is '(' when , Cannot form a valid bracket substring that ends with the current character ;
2. If the current character is ')' when :
2.1 i-1 The character of the position is ’(', At this time, this character forms a valid bracket with the previous character , Directly to dp[i-2]+2 that will do , But consider i-2 Is it greater than 0;
2.2 i-1 The character of the position is ')', At this point, if you want to form a valid string "..(.....))" The following conditions must be met :
1.dp[i - 1] Greater than 0, Because the middle of these two brackets must also be valid brackets , A set of parentheses outside a set of invalid parentheses is also invalid ;
2.i - dp[i - 1] - 1 Greater than or equal to zero ,i - dp[i - 1] - 1 namely i The position of the corresponding left parenthesis ;
3. The position of the corresponding left bracket should be '(' Otherwise, invalid parentheses ;
4. After meeting the above conditions , It can be judged that dp[i] Greater than or equal to dp[i - 1] + 2, Because this may happen :"()(())", In this example, when dp[5]=2,dp[6]=6, This is because after connecting the left bracket of the corresponding position , If there are valid parentheses on the left of the left parenthesis, they should be counted together .
class Solution {
public int longestValidParentheses(String s) {
int ans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++){
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
if (i >= 2) dp[i] = dp[i - 2] + 2;
else dp[i] = 2;
}else if (i - dp[i - 1] - 1>= 0 > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
ans = ans > dp[i] ? ans : dp[i];
}
}
return ans;
}
}
边栏推荐
- JS Vanke banner rotation chart JS special effect
- Failure causes and optimization methods of LTE CSFB
- After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
- 自动化测试的好处
- ESP32(基于Arduino)连接EMQX的Mqtt服务器上传信息与命令控制
- /usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
- On Data Mining
- Python book learning notes - Chapter 09 section 01 create and use classes
- How can programmers resist the "three poisons" of "greed, anger and ignorance"?
- The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
猜你喜欢
[optimization model] Monte Carlo method of optimization calculation
登录mysql输入密码时报错,ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: NO/YES
Développement d'un module d'élimination des bavardages à clé basé sur la FPGA
Simple blog system
C language circular statement
Do you know cookies, sessions, tokens?
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
如何修改表中的字段约束条件(类型,default, null等)
Web components series (VII) -- life cycle of custom components
【PSO】基于PSO粒子群优化的物料点货物运输成本最低值计算matlab仿真,包括运输费用、代理人转换费用、运输方式转化费用和时间惩罚费用
随机推荐
How to standardize the deployment of automated testing?
Ethernet port &arm & MOS &push-pull open drain &up and down &high and low sides &time domain and frequency domain Fourier
Use js to complete an LRU cache
Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
C mouse event and keyboard event of C (XXVIII)
[prediction model] difference method model
[FPGA tutorial case 12] design and implementation of complex multiplier based on vivado core
Blue Bridge Cup - Castle formula
Prime protocol announces cross chain interconnection applications on moonbeam
阿里测试师用UI自动化测试实现元素定位
Facebook等大厂超十亿用户数据遭泄露,早该关注DID了
Align items and align content in flex layout
Blue Bridge Cup - day of week
P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
Flask learning and project practice 8: introduction and use of cookies and sessions
3分钟带你了解微信小程序开发
Alibaba testers use UI automated testing to achieve element positioning
After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
C (thirty) C combobox listview TreeView
Interface idempotency