Problem:
Given a string containing parantheses ( (,).{,},[,]) check if the parantheses match or not.
For example,
The string “()[]{}” is a valid string because the opening parentheses are matched by closing ones.
The string “{[()]}” is also a valid expression since all the opening parentheses have corresponding closing parentheses
The string “(]” is invalid .
The string “({)}” is also invalid though there are matching parantheses because they are not in the correct positions.
For every opening parentheses , whatever parentheses comes in between the opening and closing parentheses should be closed.
Try out the solution here:
https://leetcode.com/problems/valid-parentheses/
Solution:
Hint:
- Use a stack data structure
ALGORITHM:
STEP 1: Initialize a stack to store the parenthesis
STEP 2: For every character in the string , check the top character in the stack.
STEP 2a: If the current character is the closing parenthesis of the top character then pop it out, else add the character to the stack.
STEP 3: If the stack is empty at the end , then the given string is valid , return true . Else return false.
Code:
class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); for(char c: s.toCharArray()){ boolean popped = false; if(!stack.empty()){ char top = stack.peek(); if(top == '(' && c == ')' || top == '{' && c == '}' || top == '[' && c == ']'){ popped = true; stack.pop(); } } if(!popped){ stack.push(c); } } if(stack.empty()){ return true; } return false; } }
Time complexity is O(n) where n is the length of the string and space complexity is also O(n) to store the n characters in the stack.
That’s it!