leetcode字符串

发表于

32. 最长有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
     * 可以直接使用栈来做，栈中存放的是下标。
     * 当元素是'('，直接入栈下标，当元素是')'且栈顶是'('，将栈顶出栈，并且减去栈顶下标，然后就得到当前合法序列的长度
     * */
public int longestValidParentheses(String s) {
    if(s==null||s.length()==0){
        return 0;
    }
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int res = 0;
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)=='('){
            stack.push(i);
        }else{
            stack.pop();
            if(stack.isEmpty()){
                stack.push(i);
            }else{
                res = Math.max(res,i-stack.peek());
            }
        }
    }
    return res;
}


public int longestValidParentheses(String s) {
    int[] dp = new int[s.length()];
    int res = 0;
    int max = 0;
    //假如直接是'('，那么dp[i]直接等于0,如果是')'，那么需要看i-dp[i-1]-1个位置是否是'('，假如是的话+2，还需要再看i-dp[i-1]-1前一个位置的dp
    for(int i=1;i<s.length();i++){
        if(s.charAt(i)==')'){
            int pre = i-dp[i-1]-1;
            if(pre>=0&&s.charAt(pre)=='('){
                dp[i] = dp[i-1]+2+(pre-1>=0?dp[pre-1]:0);
                max= Math.max(max,dp[i]);
            }
        }
    }
    return max;
}

20.有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)==']'||s.charAt(i)==')'||s.charAt(i)=='}'){
            if(!stack.isEmpty()){
                char c1 = stack.pop();
                if(!isSym(c1,s.charAt(i))){
                    return false;
                }
            }else{
                return false;
            }
        }else{
            stack.push(s.charAt(i));
        }
    }
    return stack.isEmpty();
}
public boolean isSym(char c1,char c2){
    return (c1=='('&&c2==')')||(c1=='['&&c2==']')||(c1=='{'&&c2=='}');
}