20. Valid Parentheses

LeetCode
,

Stack (My Solution)

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

Remarks:

  1. java character stack: Stack<Character> lefts = new Stack<>(); but not <char>
  2. Return lefts.isEmpty();, if some parentheses was not closed

Formatted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');

        for (char c : s.toCharArray()) {
            if (mapping.containsValue(c)) {
                stack.push(c);
            } else if (mapping.containsKey(c)) {
                if (stack.isEmpty() || mapping.get(c) != stack.pop()) {
                    return false;
                }
            }
        }

        return stack.isEmpty();        
    }
}

Remarks:

  1. Use more time than the simple one: HashMap takes time to initialize
  2. Use HashMap to make code cleaner