leetcode-java/src/ValidParentheses20.java at master · fluency03/leetcode-java · 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
115
116
117
118
119
120
121
122
123
124
125
126
127
/**
 * Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
 * determine if the input string is valid.
 *
 * The brackets must close in the correct order, "()" and "()[]{}" are all
 * valid but "(]" and "([)]" are not.
 */


import java.util.Map;
import java.util.HashMap;
import java.util.Stack;


public class ValidParentheses20 {
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();

        Stack st = new Stack();

        for (char c: chars) {

            if (isBackP(c)) {
                if (st.empty()) {
                    return false;
                } else {
                    char top = (char) st.pop();
                    if (c != top) {
                        return false;
                    }
                }
            } else {
                st.push(pair(c));
            }
        }

        return st.empty();
    }

    private boolean isBackP(char c) {
        return c == '}' || c == ']' || c == ')';
    }

    private char pair(char c) {
        if (c == '{') {
            return '}';
        } else if (c == '[') {
            return ']';
        } else {
            return ')';
        }
    }


    /**
     * https://discuss.leetcode.com/topic/27572/short-java-solution
     */
    public boolean isValid2(String s) {
      	Stack<Character> stack = new Stack<Character>();
      	for (char c : s.toCharArray()) {
        		if (c == '(')
        			  stack.push(')');
        		else if (c == '{')
        			  stack.push('}');
        		else if (c == '[')
        			  stack.push(']');
        		else if (stack.isEmpty() || stack.pop() != c)
        			  return false;
      	}
      	return stack.isEmpty();
    }


    public boolean isValid3(String s) {
        if (s == null || s.length()%2 == 1) return false;
        if (s.length() == 0) return true;

        Stack<Character> st = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
                continue;
            }

            if (st.isEmpty()) return false;

            switch (c) {
                case ')':
                    if (st.peek() == '(') {
                        st.pop();
                        break;
                    } else {
                        return false;
                    }
                case ']':
                    if (st.peek() == '[') {
                        st.pop();
                        break;
                    } else {
                        return false;
                    }
                case '}':
                    if (st.peek() == '{') {
                        st.pop();
                        break;
                    } else {
                        return false;
                    }
                default: return false;
            }

        }

        return st.isEmpty();
    }


    public static void main(String[] args) {
        ValidParentheses20 vp = new ValidParentheses20();

        System.out.println(vp.isValid("["));
        System.out.println(vp.isValid("]"));
        System.out.println(vp.isValid("[]"));
    }

}