Wednesday, 12 July 2017

20 Valid Parentheses

Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Approach: The idea is to use Stack and implement the following algorithm:
  1. if the current character is an opening bracket (of any type), push it to the stack and continue with the next character
  2. else if the current character is a closing bracket, following cases apply:
    1. if stack is empty - return error and exit
    2. else if the current character and the stack top forms matching parenthesis i.e. opening and closing brackets are of same type, pop the stack top and continue with the next character otherwise return error and exit
  3. Return error if the stack is not empty after all the characters are exhausted otherwise successful

class Solution {
public:
    
    int isMatching(stack<char> &stk, char c){
        if(stk.empty()){
            return 0;
        }
        char topC = stk.top();
        if( (topC == '(' && c == ')') || (topC == '{' && c == '}') || (topC == '[' && c == ']') )
            return 1;
        return 0;
    }
    
    bool isValid(string s) {
        stack<char> stk;
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                    stk.push(s[i]);
                    continue;
            } else if((s[i] == ')' || s[i] == '}' || s[i] == ']') && isMatching(stk, s[i])){
                stk.pop();
                continue;
            }
            return false;
        }
        if(!stk.empty())
            return false;
        return true;
    }
};

Here is the link to the ideone solution : http://ideone.com/jzfJnv
Share:

0 comments:

Post a Comment

Contact Me

Name

Email *

Message *

Popular Posts

Blog Archive