Valid Parentheses (E)
題目
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 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "([)]"
Output: false
題意
給定一個只包含括號的字串，判斷括號是否匹配，
思路
用堆疊處理：是左半邊括號則壓入堆疊，是右半邊括號則比較與堆疊頂是否匹配，最后檢查堆疊是否清空，
代碼實作
Java
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')') {
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else {
return false;
}
} else if (c == ']') {
if (!stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else {
return false;
}
} else {
if (!stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
}
JavaScript
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
let stack = []
for (let c of s.split('')) {
switch (c) {
case '(':
case '[':
case '{':
stack.push(c)
break
case ')':
if (stack.length === 0 || stack.pop() !== '(') {
return false
}
break
case ']':
if (stack.length === 0 || stack.pop() !== '[') {
return false
}
break
case '}':
if (stack.length === 0 || stack.pop() !== '{') {
return false
}
break
}
}
return stack.length === 0
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41140.html
標籤：其他