LeetCode Study : 20. Valid Parentheses

問題

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

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

自分の解答

public boolean isValid(String s) {
    char[] chars = s.toCharArray();
    Stack<Character> stack = new Stack<>();
    for (char c : chars) {
        if (stack.size() == 0) {
            stack.add(c);
            continue;
        }
        if (isPair(stack.peek(), c)) {
            stack.pop();
        } else {
            stack.add(c);
        }
    }
    return stack.size() == 0;
}

private boolean isPair(Character c1, Character c2) {
    return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') || (c1 == '[' && c2 == ']');
}

コード理解

別解

class Solution {
  private HashMap<Character, Character> mappings;

  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();

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

      if (this.mappings.containsKey(c)) {
        char topElement = stack.empty() ? '#' : stack.pop();
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        stack.push(c);
      }
    }
    return stack.isEmpty();
  }
}

Time : / Space :

(){}[]のセットを保持するMapを作成せず、汚い比較メソッドisPairを書いて妥協してしまった。計算量が全然違うのでちゃんと書かないと。 あと、入力値が例えば"((])){}"のとき、((]の時点でfalseを返せるはずなのにそのケアをしてない。 スムーズに書けたからといって調子に乗らないの大事。。。

Stackのメソッドがうまく使えていない。 size() == 0ではなく empty()(Stackクラス）またはisEmpty(Vectorクラス)を使えるし、add(Vector)じゃなくてpushだよね。pop書いてるんだから気づけ。

今後のための考え方

• 文字列比較は妥協せずにHashMapで高速に
• 最後まで舐めきってからtrue/false返すでなく途中で返せないか吟味する
• 調子に乗らない
• Stack#push, emptyを使おう