Question

Formatted question description: https://leetcode.ca/all/20.html

20	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.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

@tag-stack

Algorithm

Here you need to use a stack to start traversing the input string. If the current character is the left half bracket, it will be pushed onto the stack. If the right half bracket is encountered, if the stack is empty at this time, it will directly return false, such as If it is not empty, remove the top element of the stack, if it is the corresponding left half bracket, continue to loop, otherwise return false.

Pitfalls

  1. After the final for is over, it depends on whether the stack is empty or not, if it is all “((((((“)
  2. When popping, did not check if the stack is empty

Code

Java

import java.util.Stack;

public class Valid_Parentheses {

	public class Solution {

	    public boolean isValid(String s) {

	        if (s == null || s.length() == 0)   return false;

	        Stack<Character> sk = new Stack<>();

	        for (int i = 0; i < s.length(); i++) {
	            char c = s.charAt(i);
	            if (c == '(' || c == '{' || c == '[')   sk.push(c);
	            else if (c == ')' || c == '}' || c == ']') {

	                // @note: I missed stack check
	                if (sk.isEmpty())   return false;

	                char pop = sk.pop();
	                if (!valid(pop, c))   return false;
	            }
	            else    return false; // some other chars except parenthesis
	        }


	        // @note: i missed sanity check, what if only "["
	        return sk.isEmpty() ? true : false;
	    }

	    public boolean valid(char left, char right) {

	        return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
	    }
	}

}

All Problems

All Solutions