[알고리즘문제] 릿코드 Valid Parentheses

leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

정상적인 괄호 양식이 맞는 경우 true, 정상적인 양식이 아닐 경우 false를 return하는 문제

간단하게 stack을 이용하여 해결 가능하다.

 

time complexity : O(n)

space complexity : O(n)

#include<iostream>
#include<stack>

using namespace std;

class Solution {
private:
    stack<char> st;
public:
    Solution(){}
    ~Solution() {
        for (int i = 0; i < st.size(); i++) st.pop();
    }
    bool isValid(string s) {       
        for (int i = 0; i < s.size(); i++) {
            //여는 괄호이면 stack에 push
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                st.push(s[i]);
                continue;
            }
            //stack이 비어있는데 닫는 괄호이면 false
            if (st.empty()) {
                if (s[i] == ')' || s[i] == '}' || s[i] == ']') return false;
            }
            //현재 문자가 닫는 괄호인데 이전 문자가 같은 괄호의 개행문자가 아닐경우 false
            if (s[i] == ')' && !st.empty() && st.top() != '(') {
                return false;
            }
            if (s[i] == '}' && !st.empty() && st.top() != '{') {
                return false;
            }
            if (s[i] == ']' && !st.empty() && st.top() != '[') {
                return false;
            }
            if(!st.empty()) st.pop();
        }
        //모든 문자열을 돌고 난 후 stack에 문자가 남아있다면 false
        if (!st.empty()) return false;
        
        //모든 검사 완료 후 true
        return true;
    }
};

int main() {
    Solution s;
    cout << s.isValid("()");
	return 0;
}

rust 코드

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut st : Vec<char> = Vec::new();
        for c in s.chars(){
            if c == '(' || c == '[' || c == '{' {
                st.push(c);
                continue;
            }
            if st.is_empty(){
                if c == ')' || c == '}' || c == ']' { return false; }
            }
            if c == ')' && !st.is_empty() && st[st.len() - 1] != '(' { return false; }
            if c == '}' && !st.is_empty() && st[st.len() - 1] != '{' { return false; }
            if c == ']' && !st.is_empty() && st[st.len() - 1] != '[' { return false; }
            if !st.is_empty(){
                st.pop();
            }
        }
        if !st.is_empty() { return false; }
        true
    }
}

typescript 코드

export function isValid(s : string) : boolean {
    let st : string[] = [];
    const brackets = {
        '(' : ')',
        '{' : '}',
        '[' : ']'
    }
    for(let i = 0; i < s.length; i++){
        if(s[i] === '(' || s[i] === '{' || s[i] === '[') st.push(s[i]);
        else if(brackets[st.pop()] !== s[i]) return false;
    }

    return true;
}