20. Valid Parentheses

LeetCode 영어 문제

 

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

 

번역

 

'(', ')', '{', '}', '['및 ']'문자 만 포함 된 문자열이 있으면 입력 문자열이 유효한지 판별하십시오.

다음과 같은 경우 입력 문자열이 유효합니다. 열린 브래킷은 동일한 유형의 브래킷으로 닫아야합니다.

열린 브래킷은 올바른 순서로 닫아야합니다. 빈 문자열도 유효한 것으로 간주됩니다.

예 1 : 입력 : "()" 출력 : true

예 2 : 입력 : "() [] {}" 출력 : true

예 3 : 입력 : "(]" 출력 : false

예 4 : 입력 : "([)]" 출력 : false

예 5 : 입력 : "{[]}" 출력 : true

 

다른 사람의 풀이

 

class Solution {

  // Hash table that takes care of the mappings.
  private HashMap<Character, Character> mappings;

  // Initialize hash map with mappings. This simply makes the code easier to read.
  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {

    // Initialize a stack to be used in the algorithm.
    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      // If the current character is a closing bracket.
      if (this.mappings.containsKey(c)) {

        // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
        char topElement = stack.empty() ? '#' : stack.pop();

        // If the mapping for this bracket doesn't match the stack's top element, return false.
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        // If it was an opening bracket, push to the stack.
        stack.push(c);
      }
    }

    // If the stack still contains elements, then it is an invalid expression.
    return stack.isEmpty();
  }
}

class Solution {
    public boolean isValid(String s) {
        if (s.isEmpty()) {
            return true;
        }
        char[] stack = new char[s.length()];
        int head = 0;
        for (char c : s.toCharArray()) {
            switch (c){
                case '{': 
                    stack[head++] = '}'; 
                    break;
                case '[': 
                    stack[head++] = ']'; 
                    break;
                case '(': 
                    stack[head++] = ')'; 
                    break;
                default:
                    if (head == 0 || stack[--head] != c) {
                        return false;
                    }
            }
        }
        return head == 0;
    }
} 

 

여니여니의 해석

 

 

 

출처 sources

• https://leetcode.com/problems/valid-parentheses/solution/

Valid Parentheses - LeetCode