Valid Parentheses

 Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Solution

public static boolean isValidOrNot(String s) {
		boolean isValid = true;
		if (s.length() % 2 == 1) {
			isValid = false;
		} else {
			Stack<Character> stack = new Stack<Character>();
			for (char c : s.toCharArray()) {
				if (c == '(') {
					stack.add(')');
				} else if (c == '[') {
					stack.add(']');
				} else if (c == '{') {
					stack.add('}');
				} else {
					if (!stack.isEmpty() && c == stack.peek()) {
						stack.pop();
					} else {
						isValid = false;
						break;
					}
				}
			}
			if (!stack.isEmpty()) {
				isValid = false;
			}
		}
		System.out.println(isValid);
		return isValid;
	}

The above solution took 1ms for most of the cases, so tried to optimise to make it faster. Just for fun tried in leetcode, It took 0ms :)

 

public static void main(String[] args) {
		String s = "((";
		boolean isValid = true;
		if (s.length() % 2 == 1) {
			isValid = false;
		} else {
			int[] chatArray = new int[s.length()];
			int i = 0;

			for (char c : s.toCharArray()) {
				if (c == '(') {
					chatArray[i++] = ')';
				} else if (c == '[') {
					chatArray[i++] = ']';
				} else if (c == '{') {
					chatArray[i++] = '}';
				} else {
					if (i != 0 && c == chatArray[i - 1]) {
						i--;
					} else {
						isValid = false;
						break;
					}
				}
			}
			if (i != 0) {
				isValid = false;
			}
		}
		System.out.println(isValid);
	}

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...