Leetcode: Valid Parentheses

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.

Analysis:

1. What is a valid string?

We can list several examples to show the valid string:

• Empty string is always valid
• For string has only one pair of parentheses, (), [ ], { } are valid. However, (], {], (}, etc.. are not valid
• For string has two pairs of parentheses, ( )[ ], ([ ]), { }[ ] are valid. However, ( [ ) ], ( { } ] are not valid
• For string has  three pairs of parentheses, ( )[ ]{ }, { ( [ ] ) } are valid. However, { [ )} ( ] is not valid

Now we can use these examples to check if a string is valid. In addition, if the length of a given string is odd, it must be invalid. 

2. The problem presumes that the input string has just the characters of parentheses, square brackets, and brace. So we don't need to  consider other characters like white space, digit, etc... 

3. How to determine if a string is valid?

There are two conditions that a valid string must fulfill:

• The numbers of parentheses must match. For example, if there is a left parentheses, there must have a right one, so does for square brackets and brace. Therefore, the number of left parentheses must be equal to the right parentheses. 
• The brackets must be in the correct closing order. For example, { [ } ], although this string fuifills the first requirement, it is not the correct order. So how to determine the order is correct? Last-in-First-out. For instance, { ( ) } is valid because we see left brace first, we will see the right brace last. So you might already come out the idea! Yes, we can use a stack to store the parentheses. 
• Note that the problem does not require the order of the parentheses, i.e. { } should be outside of [ ], while [ ] must be outside of ( )

Solution:

According to the analysis, we can use the stack to solve this problem. 

• When we see a left parenthesis, (, [, or {, we push it into the stack. 
• When we see a right parenthesis, we pop the top element from the stack, and compare it with the right parentheses. If they are matched, check next character in the string; otherwise, directly returns the false. 
• If the stack is empty while the string has not reached the end, it must be the situation like ( ) ], then it returns the false.
• If the stack is not empty while the string has already reached the end, it must be the situation like ( ( ) then it returns the false. 

Now let's look at the implementation in Java.

Code (Java): 

public class Solution {
    public boolean isValid(String s) {
        final int length = s.length();
        if (length == 0) return true;
        if (length % 2 == 1) return false;
        
        Stack<Character> stack = new Stack<Character>();
        
        int index = 0;
        while (index < length) {
            char cur = s.charAt(index);
            if (isLeftBracket(cur)) {
                stack.push(cur);
                index++;
            }
            else if (isRightBracket(cur)) {
                if (stack.empty()) return false;
                char temp = stack.pop();
                if (!isPair(temp, cur)) return false;
                index++;
            }
        }
        return stack.empty();
    }
    
    // Determine the given parentheses is left
    private boolean isLeftBracket(char ch) {
        if (ch == '(' || ch == '[' || ch == '{') return true;
        else return false;
    }
    
    // Determine the given parentheses is right
    private boolean isRightBracket(char ch) {
        if (ch == ')' || ch == ']' || ch == '}') return true;
        else return false;
    }
    
    // Determine the left and right parentheses is a pair
    private boolean isPair(char left, char right) {
        if ((left == '(' && right == ')') || 
            (left == '[' && right == ']') || 
            (left == '{' && right == '}')
           )
         return true;
         else return false;
    }
}

Discussion:
Now we analyze the solution. Since we only iterate the input string only once, the time complexity is O(n). We need a stack to store the left parentheses. In the worst case the space is O(n). E.g. for the input string ( ( ( ( ( ( ( ( ( (. We just push the left parentheses into the stack until the end of the string. 


Summary:
In this problem we used the Java stack to have the parentheses pairing problem. Actually the stack is widely used in such kinds of pairing problem. Furthermore, you may notice that in the implementation, we used many modular programming paradigm, which is preferred in the code interview. We could firstly define the method and explain what does this mean, and implement it later. Sometimes you don't even need to implement those details. But this programming paradigm makes the coding looks neat.