本篇為LeetCode上演算法的簡單問題, Valid Parentheses 有效括號。
題目如下:
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 1:Example 2:Input: "()" Output: true
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);
}
}
沒有留言:
張貼留言