LeetCode Valid Parentheses 有效括號

本篇為LeetCode上演算法的簡單問題， Valid Parentheses 有效括號。

題目如下：

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

這題是要判斷由括弧字元'('，')'，'['，']'，'{'，'}'組成的字串是否滿足左右成對且以正確的順序閉合。空字串是為有效。

例如下面幾個字串都是無效的。

• ")"
• "["
• "([)]"
• "(]"
• ")[]{()}"

下面字串則是有效的

• ""
• "()"
• "()[]{}"
• "{[]}"

作法為準備一個Stack容器，然後從字串最左邊的括弧開始看，如果是左括弧就直接放入Stack裡，如果是右括弧就先把Stack最上面的左括弧取出，並看看這個左括弧應搭配哪一種右括弧，如果應搭配的右括弧與目前手上的右括弧不同，那代表這個字串中的括弧是無效的，也就是字串中的括弧順序錯誤無法兩兩成對正確的閉合。

class Solution {
    
    private final static Set<Character> lpSet = new HashSet<>();
    private final static Set<Character> rpSet = new HashSet<>();
    private final static Map<Character, Character> lpMap = new HashMap<>();

    static {
        lpSet.add('(');
        lpSet.add('[');
        lpSet.add('{');
        rpSet.add(')');
        rpSet.add(']');
        rpSet.add('}');

        lpMap.put('(',')');
        lpMap.put('[',']');
        lpMap.put('{','}');
    }
    
    public boolean isValid(String s) {
        if (s.length() == 0) { // 空字串判定為有效
            return true;
        }
        if ((s.length() & 1) != 0) { // 字串長度為奇數判定為無效
            return false;
        }

        char[] pp = s.toCharArray();
        Stack<Character> stack = new Stack<>(); // 使用Stack容器來裝左括弧

        for (int i = 0; i < pp.length; i++) {
            if(i == 0 && isRightParentheses(pp[i])) { // 如果第一個字元為右括弧判定為無效
                return false;
            }

            if (isLeftParentheses(pp[i])) { // 如果是左括弧放進Stack容器
                stack.push(pp[i]);
            } else if (isRightParentheses(pp[i])) { // 如果是右括弧，
                 char lp = stack.pop();             // 從Stack容器拿出最上面的左括弧，
                 char expectedRp = lpMap.get(lp);   // 取得左括弧預期搭配的右括弧，
                 char rp = pp[i];                   // 實際的右括弧
                 if (expectedRp != rp) {            // 比對預期的右括弧是否等於實際的右括弧，若不同則判定無效。
                     return false;
                 }

            }

        }

        if (stack.size() > 0) { // 結束後Stack容器若還存在任何左括弧，則判定無效
            return false;
        }

        return true;
    }
    /** 是否為左括弧 */
    private boolean isLeftParentheses(char p) {
        return lpSet.contains(p);
    }
    /** 是否為右括弧 */
    private boolean isRightParentheses(char p) {
        return rpSet.contains(p);
    }
}