問題

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

Note that an empty string is also considered valid.

解答

問題文を読んでExampleを見た瞬間にStackだなと思ったので、それで実装しました。スタック - Wikipedia

import java.util.LinkedList;
class Solution {
    public boolean isValid(String s) {
    LinkedList<Character> parenthesesStack = new LinkedList<>();
    for (char ch : s.toCharArray()) {
      if (ch == '(' || ch == '{' || ch == '[') {
        parenthesesStack.push(ch);
      } else if (!parenthesesStack.isEmpty()) {
        char openParentheses = parenthesesStack.pop();
        if (!(openParentheses == '(' && ch == ')')
            && !(openParentheses == '{' && ch == '}')
            && !(openParentheses == '[' && ch == ']')) {
          return false;
        }
      } else {
        return false;
      }
    }
    return parenthesesStack.isEmpty();
  }
}

時間計算量：O(n)、メモリ計算量：O(n)

他の人の解答はこんな感じです。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for(char c : s.toCharArray()){
            if(c=='(' || c=='[' || c=='{')
                stack.push(c);
            else if(!stack.isEmpty() && isMatch(stack.peek(),c)) {
                stack.pop();
            } else{
                return false;
            }
               
        }
        
        return stack.isEmpty()? true : false;
    }
    
    public boolean isMatch(char a, char b ){
       return  (a=='('&& b==')'|| a=='{' && b =='}' || a=='[' && b==']') ? true : false;
    }
}

時間計算量：O(n)、メモリ計算量：O(n)

やっていることは全く同じなのですが、三項演算子を使って foo ? true : false はちょっと拒絶反応が出ますね。。。