有效括号问题合集

力扣20 有效的括号 

public boolean isValid(String s){
        if(s.isEmpty()) return true;
        Stack stack=new Stack<>();
        for(char c:s.toCharArray()){
            if(c=='(') stack.push(')');
            else if(c=='{') stack.push('}');
            else if(c=='[') stack.push(']');
            else if(stack.isEmpty()||c!=stack.pop()) return false;
        }
        return stack.isEmpty();
    }

力扣32 最长有效括号

方法一：栈

public int longestValidParentheses(String s){
        if(s.isEmpty()||s==null) return 0;
        Stack stack=new Stack<>();
        stack.push(-1);
        int res=0;
        for(int i=0;i 
方法二：动态规划
 

 ​​​​​​​
 
public int longestValidParentheses(String s){
        int[] dp=new int[s.length()];
        int res=0;
        for(int i=1;i=2?dp[i-2]:0)+2;
                }
                else if(i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i]=dp[i-1]+2+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0);
                }
                res=Math.max(res,dp[i]);
            }
        }
        return res;
    }