Leetcode
2020.04.25 15:57

20. Valid Parentheses

조회 수 102 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true


/*
class Solution {
    public boolean isValid(String s) {
        Map<Character, Integer> hmap = new HashMap<>();
        Map<Character, Character> pairs = new HashMap<>();
        
        pairs.put(')', '(');
        pairs.put('}', '{');
        pairs.put(']', '[');
        
        for(int i=0; i<s.length(); i++){
            Character ch = s.charAt(i);
            
            if(ch == '(' || ch == '{' || ch == '['){
                hmap.put(ch, hmap.getOrDefault(ch,0)+1);
            }else if(ch == ')' || ch == '}' || ch == ']'){
                Character pair = pairs.get(ch);
                
                if(hmap.containsKey(pair) == false){
                    return false;
                }
                
                hmap.put(pair, hmap.get(pair)-1);
                System.out.println(hmap);
                System.out.println("-> "+pair);
                
                if(hmap.get(pair) == 0){
                    hmap.remove(pair);
                }
            }
        }
        
        return hmap.isEmpty();
    }
}
*/
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = new HashMap<>();
        
        pairs.put(')', '(');
        pairs.put('}', '{');
        pairs.put(']', '[');
        
        for(int i=0; i<s.length(); i++){
            Character ch = s.charAt(i);
            
            if(ch == '(' || ch == '{' || ch == '['){
                stack.push(ch);
            }else if(ch == ')' || ch == '}' || ch == ']'){
                if(stack.empty()){
                    return false;
                }

                if(stack.peek() == pairs.get(ch)){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}


class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = new HashMap<>();
        
        pairs.put(')', '(');
        pairs.put('}', '{');
        pairs.put(']', '[');
        
        for(int i=0; i<s.length(); i++){
            Character ch = s.charAt(i);
            
            //if(ch == '(' || ch == '{' || ch == '['){
            if(pairs.containsValue(ch)){
                stack.push(ch);
            //}else if(ch == ')' || ch == '}' || ch == ']'){
            }else if(pairs.containsKey(ch)){
                if(stack.empty()){
                    return false;
                }
                
                if(stack.peek() == pairs.get(ch)){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}

[문제] https://leetcode.com/problems/valid-parentheses/



?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
37 Leetcode 415. Add Strings hooni 2020.04.28 121
36 Leetcode 7. Reverse Integer hooni 2020.04.28 104
35 Leetcode 206. Reverse Linked List hooni 2020.04.28 114
34 Leetcode 53. Maximum Subarray hooni 2020.04.28 110
33 Leetcode 581. Shortest Unsorted Continuous Subarray hooni 2020.04.28 111
32 Leetcode 852. Peak Index in a Mountain Array hooni 2020.04.28 104
31 Leetcode 350. Intersection of Two Arrays II hooni 2020.04.28 106
» Leetcode 20. Valid Parentheses hooni 2020.04.25 102
29 Leetcode 38. Count and Say hooni 2020.04.25 107
28 Leetcode 937. Reorder Data in Log Files hooni 2020.04.25 111
27 Leetcode 443. String Compression hooni 2020.04.25 107
26 Leetcode 437. Path Sum III hooni 2020.04.24 144
25 Leetcode 54. Spiral Matrix hooni 2020.04.20 126
24 Leetcode 380. Insert Delete GetRandom O(1) hooni 2020.04.18 128
23 Leetcode 542. 01 Matrix hooni 2020.04.18 127
22 Leetcode 139. Word Break hooni 2020.04.18 133
21 Leetcode 126. Word Ladder II hooni 2020.04.17 131
20 Leetcode 238. Product of Array Except Self hooni 2020.04.17 129
19 Leetcode 763. Partition Labels hooni 2020.04.17 163
18 Leetcode 121. Best Time to Buy and Sell Stock hooni 2020.04.17 129
Board Pagination Prev 1 2 3 4 Next
/ 4