83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[4544,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1d:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:T5fb,

Problem

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Examples

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

More Examples

80%

Follow up

Only One Type of Parenthesis, Say ()

Solution

A typical problem which can be solved by using a stack data structure.

Version1 - When only 1 parenthesis type is present

Method 1 - Using Stack

Why Stack?

Since the last bracket that is opened must also be the first one to be closed, it makes sense to use a data structure that uses the Last In, First Out (LIFO) principle. Therefore, a stack is a good choice here.

1c:T72c,

Code

Here is the solution:

public static boolean isValid(String str) {
	Map<Character, Character> parenthes = new HashMap<>() {{
		put('(', ')');
		put('{', '}');
		put('[', ']');
	}};

	Stack<Character> stack = new Stack<>();
	for (char c : s.toCharArray()) {
		if (parenthese.containsKey(c)) {
			stack.push(c);
		} else {
			if (stack.isEmpty()) {
				return false;
			}
			char cKey = stack.pop();

			char cVal = parenthese.get(cKey);

			if (cVal != c) {
				return false;
			}

		}
	}

	return stack.isEmpty();
}

This is O(n) time and O(n) space solution. Can we do better with space?

We can use counter to reduce space. See method 2 with only 1 type of parenthesis.