Valid Parentheses

isValid.java

/*
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.

Algorithm:
1. Stack will be the best data structure here
2. Push char to stack if stack is empty or next char does not match the peek of stack
3. Pop from stack if the peek char is matched with next char.
4. Return true if the stack is empty, or false if not empty.
*/
public class Solution {
    public boolean isValid(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s.length() == 0) return true;
        Stack<Character> stack = new Stack<Character>();
        stack.push(s.charAt(0));
        int i = 1;
        while(i < s.length()) {
            if(stack.empty()) {
                stack.push(s.charAt(i));
                i++;
                continue;
            }
            char peek = stack.peek();
            if(isMatch(peek, s.charAt(i))) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
            i++;
        }
        return stack.empty() ? true : false;
    }
    public boolean isMatch(char a, char b) {
        if(a == '(' && b == ')') return true;
        if(a == '[' && b == ']') return true;
        if(a == '{' && b == '}') return true;
        return false;
    }
}