Leetcode Valid Parentheses problem solution

YASH PAL,

In this Leetcode Valid Parentheses problem solution we have 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.
Leetcode Valid Parentheses problem solution

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; 
}

coding problems