LeetCode 솔루션

[Easy - wk1 - Q4] 20. Valid Parentheses

Chloe 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.03 14:53

7,869 조회
4 댓글
0 추천
0 비추천
목록 게시글 쓰기

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

#leetcode, #문제풀이, #easy, #amazon, #linkedin, #facebook, #microsoft, #bloomberg, #spotify, #apple, #adobe, #expedia, #google, #vmware, #oracle, #cisco, #yandex, #intel, #tiktok, #arista networks, #barclays, #servicenow, #zillow, #goldman sachs, #booking.com, #salesforce, #netflix, #dataminr, #tcs, #string, #stack

링크

https://leetcode.com/problems/valid-parentheses/ 16131 회 연결

익명
작성일 2022.05.04 10:40

class Solution:
    def isValid(self, s: str) -> bool:
        valid = {')':'(', ']':'[', '}':'{'}
        tmp = []
        for i in s:
            if i not in valid:
                tmp.append(i)
            else:
                if tmp and tmp[-1] == valid[i]:
                    tmp.pop()
                else:
                    return False
                
        return len(tmp) == 0

익명
작성일 2022.05.05 04:38

class Solution {
    
    private HashMap<Character, Character> map = new HashMap<Character, Character>();
    public boolean isValid(String s) {
        
        initMap();
        Stack<Character> stack = new Stack<Character>();
        
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                char top = stack.isEmpty()? 'c' : stack.pop();
                if(top != map.get(ch)){
                    return false;
                }
            }else{
                stack.push(ch);
            }
        }
        
        return stack.isEmpty();
        
    }
    
    private void initMap(){
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
    }
}

익명
작성일 2022.05.08 20:05

class Solution:
    def isValid(self, s: str) -> bool:

        while ('()' in s) or ('[]' in s) or ('{}' in s):
            s = s.replace('()', '').replace('[]', '').replace('{}', '')
        return s==''

익명
작성일 2022.05.09 00:05

Python

Runtime: 56 ms, faster than 21.31% of Python3 online submissions for Valid Parentheses.
Memory Usage: 14 MB, less than 25.60% of Python3 online submissions for Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        table={
            ')':'(',
            '}':'{',
            ']':'['
        }
        
        for char in s:
            if char not in table:
                stack.append(char)
            elif not stack or table[char] != stack.pop():
                return False
        return len(stack) == 0