LeetCode/src/hard/LongestValidParentheses.java at master · chenyiAlone/LeetCode · GitHub

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package hard;

import java.util.LinkedList;

/**
 *
 * ClassName: LongestValidParentheses
 * @author chenyiAlone
 * Create Time: 2018/12/13 08:41:21
 * Description: No.32
 *
 * Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

    Example 1:

    Input: "(()"
    Output: 2
    Explanation: The longest valid parentheses substring is "()"
    Example 2:

    Input: ")()())"
    Output: 4
    Explanation: The longest valid parentheses substring is "()()"
 */
public class LongestValidParentheses {


    public int longestValidParentheses(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        int start = -1;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    start = i;

                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        res = Math.max(res, i - start);
                    } else {
                        res = Math.max(res, i - stack.peek());
                    }
                }
            }
        }
        return res;
    }
    public int longestValidParentheses_Error(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        int ans = 0;
        int count = 0;
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            System.out.println(i);
            Character c = s.charAt(i);
            System.out.println("c = " + c);
            if (c.charValue() == '(') {
                if (flag) {
                    flag = !flag;
                } else {
                    ans = Math.max(ans, count);
                    count = 0;
                }
                stack.push(c);
            } else if (c.charValue() == ')') {
                Character headC = stack.peek();
                System.out.println("headC = " + headC);
                if (headC != null && headC.charValue() == '(') {
                    stack.pop();
                    count += 2;
                    flag = true;
                } else {
                    ans = Math.max(ans, count);
                    count = 0;
                    stack.push(c);
                    flag = false;
                }
                System.out.println("ans" + ans);
//                System.out.println("i = " + i + "  c = " + c  + "  headC = " + stack.peek() + "  stack = " + stack);
            }
        }
        ans = Math.max(ans, count);
        return ans;
    }

    /*
    public int longestValidParentheses(String s) {
        int count = 0, ans = 0;
        LinkedList<Character> list = new LinkedList<>();
        for (Character c : s.toCharArray()) {
            System.out.println(c + "" + list.peek());
            if (c.equals('('))
                list.offer(c);
            else if (c.equals(')')) {
                if (Character.valueOf('(').equals(list.peek())) {
                    list.pop();
                    count += 2;
                    ans = Math.max(count, ans);
                } else {
                    count = 0;
                }
            }
        }
        return ans;
    }*/
    public static void main(String[] args) {
        String s = "()(()";
        System.out.println("ans = " +new LongestValidParentheses().longestValidParentheses_Error(s));
    }

}