GeetCode Hub

  1. Home
  2. GeetCode
  3. GeetCode Hub

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 '()[]{}'.

class Solution { public boolean isValid(String s) { if(s==null){ return false; } int len = s.length(); if(len == 0){ return false; } Map<Character, Character> map = new HashMap<Character, Character>(); map.put(')','('); map.put('}','{'); map.put(']','['); Stack<Character> stack = new Stack<Character>(); for(int i=0;i<s.length();i++){ char ch = s.charAt(i); if(map.containsKey(ch)){ if(stack.isEmpty()){ return false; } char top = stack.pop(); if(map.get(ch) != top){ return false; } } else{ stack.push(ch); } } return stack.isEmpty(); } }

The main gist of this question is to check the understanding of stack concepts, If you know how we can use stack and keep track of matching pairs, then it is easy to implement.

Time Complexity: O(n)

Space Complexity: O(n)

Medium
Generate Parentheses
Generate Parentheses
Hard
Longest Valid Parentheses
Longest Valid Parentheses
Hard
Remove Invalid Parentheses
Remove Invalid Parentheses
Medium
Check If Word Is Valid After Substitutions
Check If Word Is Valid After Substitutions