CODEWITHSUNDEEP
javaoptimizationstack
jignesh kumar
jignesh kumar

Reputation: 81

Optimized solution for Balanced Parentheses Problem

Given a string 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.
  3. Note that an empty string is also considered valid.

Example 1:

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

Example 2:

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

My solution for the above problem is:

static boolean isPair(char left,char right){
        return left=='{' && right=='}' || left=='(' && right==')' || left=='[' && right==']'; 
    }
    public boolean isValid(String s) {
        Stack<Character> stack= new Stack<>();
        for(char ch: s.toCharArray()){
            if(ch=='(' || ch=='{' || ch=='['){
                stack.push(ch);
            }
            else{
                if(!stack.isEmpty() && isPair(stack.peek(),ch))
                    stack.pop();
                else
                    return false;
            }
        }
        return stack.isEmpty();
}

I have found a much smarter solution somewhere but unable to understand it. Here's the code:

public boolean isValid(String s) {
        Stack<Character> stack= new Stack<>();
        for(char ch: s.toCharArray()){
            if(ch=='(')
                stack.push(')');
            else if(ch=='{')
                stack.push('}');
            else if(ch=='[')
                stack.push(']');
            else if(stack.isEmpty() || stack.pop()!=ch)
                return false;
        }
        return stack.isEmpty();
}

Please help me to understand the working of last else-if block.

Upvotes: 2

Views: 6992

Answers (4)

MD ASIF ALAM
MD ASIF ALAM

Reputation: 31

I am adding my code here using map in JavaScript, Please add if you find a way better than it.

`   var isValid = function(s) {
let map={
  ")":"(",
  "]":"[",
  "}":"{"      
}

let _stack = [];
for(let i=0;i<s.length;i++)
  {
    if(s[i]==="(" || s[i]==="[" || s[i]==="{")
      {
        _stack.push(s[i]);
      }
    else if(_stack[_stack.length-1]===map[s[i]])
      {
        _stack.pop();
      }
    else
      return false;
  }
   return  _stack.length?false:true;
  };

`

Upvotes: 0

Tal
Tal

Reputation: 1231

Javascript solution to the problem


var isValid = function (s) {
    if (s.length % 2 !== 0) return false
    // Stack to store left symbols
    const leftSymbols = [];
    // Loop for each character of the string
    for (let i = 0; i < s.length; i++) {
        // If left symbol is encountered
        if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
            leftSymbols.push(s[i]);
        }
        // If right symbol is encountered
        else if (s[i] === ')' && leftSymbols.length !== 0 && leftSymbols[leftSymbols.length - 1] === '(') {
            leftSymbols.pop();
        } else if (s[i] === '}' && leftSymbols.length !== 0 && leftSymbols[leftSymbols.length - 1] === '{') {
            leftSymbols.pop();
        } else if (s[i] === ']' && leftSymbols.length !== 0 && leftSymbols[leftSymbols.length - 1] === '[') {
            leftSymbols.pop();
        }
        // If none of the valid symbols is encountered
        else {
            return false;
        }
    }
    return leftSymbols.length === 0;
};

Upvotes: 0

Ricola
Ricola

Reputation: 2932

It is actually pretty similar to your own version.

The main difference is that you push the open brackets to the stack and in isPair check if the open bracket on top of the stack matches the closing one you're currently evaluating.

That solution skips it by directly pushing the expected closing bracket to the stack, but functionally it's the same.

That last if else does the exact same than your else:

  1. If stack.isEmpty() returns false
  2. If not empty and not matching the bracket on top of the stack, returns false
  3. Otherwise pops the bracket on top

There is a slight difference that for case 2 that solution pops the stack while in yours you don't pop it. But it doesn't change anything as the function returns and that stack will not be used anymore.

Upvotes: 0

Astik Anand
Astik Anand

Reputation: 13057

You have pushed the closing bracket for all the opening brackets. So, that when closing brackets come, then it will match the character at the top of stack. If it doesn't match or stack becomes empty. That means unbalanced.

else if(stack.isEmpty() || stack.pop()!=ch)
    return false;

When you reach here, you have a bracket as ch but the stack is empty or the value from the stack doesn't match the incoming character.

So, the parantheses are not balanced.

Upvotes: 2

Related Questions