Valid Parentheses Problem Solution

Valid Parentheses Problem: 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.
  3. Every close bracket has a corresponding open bracket of the same type.

Example :

Input: s = "()"
Output: true

Example :

Input: s = "(]"
Output: false

Problem Solution In Python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic = {'(': ')', '[': ']', '{': '}'}
        for c in s:
            if stack and stack[-1] in "([{" and dic[stack[-1]] == c:
                stack.pop()
            else:
                stack.append(c)
        return not stack

Problem Solution In Java

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

Problem Solution In C++

class Solution {
public:
    char transfer(char c) {
        char tc;
        switch (c) {
            case ')':
                tc = '(';
                break;
            case ']':
                tc = '[';
                break;
            case '}':
                tc = '{';
                break;
        }
        return tc;
    }
    
    bool isValid(string s) {
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s.at(i) == '(' || s.at(i) == '[' || s.at(i) == '{')
                st.push(s[i]);
            if (s.at(i) == ')' || s.at(i) == ']' || s.at(i) == '}') {
                if (st.empty()) return false;
                if (st.top() == transfer(s[i]))
                    st.pop();
                else
                    return false;
            }
        }
        if (!st.empty()) return false;
        else return true;
    }
};

Problem Solution In C

#define CLOSE_PAREN 3

int getType(char c) {
    int idx = 0;
    
    switch (c) {
        case '(':
        idx = 0;
        break;
        case '{':
        idx = 1;
        break;
        case '[':
        idx = 2;
        break;
        case ')':
        idx = 3;
        break;
        case '}':
        idx = 4;
        break;
        case ']':
        idx = 5;
        break;
        default:
        break;          
    }    
    return idx;
}

bool isValid(char* s) {
    char paren[] = { '(', '{', '[', ')', '}', ']' };
    int len = strlen(s);
    char *valid = (char*)calloc(len, sizeof(char));
    int k = 0;
    
    if(s == NULL || len == 1) 
        return false;
    if (len == 0)
        return true;
    
    for (int i=0; i<len; i++) {
        int type = getType(s[i]);
        
        if (type < CLOSE_PAREN) {
            valid[k++] = s[i];
        } else {
            if (k>0 && valid[k-1] == paren[type-CLOSE_PAREN]) {
                k--;
            } else {
                return false;
            }                
        }
    }
    return (k == 0) ? true: false; 
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment