給定一個(gè)只包括 '('禁灼，')'管挟，'{'，'}'弄捕，'['僻孝，']' 的字符串，判斷字符串是否有效守谓。
有效字符串需滿(mǎn)足：
左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合穿铆。
左括號(hào)必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串斋荞。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
JAVA實(shí)現(xiàn)
class Solution {
public boolean isValid(String s) {
if (s.isEmpty()){
return true;
}
if (s.length() %2 != 0) {
return false;
}
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put('}','{');
map.put(']','[');
LinkedList<Character> list = new LinkedList<>();
for (int i = s.length() - 1; i >=0 ; i--) {
char charAt = s.charAt(i);
if (map.containsKey(charAt)) {
list.add(map.get(charAt));
}else {
Character character = list.peekLast();
if (Character.valueOf(charAt).equals(character)){
list.removeLast();
}else {
return false;
}
}
}
return true;
}
}
class Solution {
public boolean isValid(String s) {
if (s.isEmpty()){
return true;
}
if (s.length() %2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
}else {
if (stack.isEmpty()) {
return false;
}
Character topChar = stack.pop();
if(c == ')' && topChar != '(') {
return false;
}
if(c == ']' && topChar != '[') {
return false;
}
if(c == '}' && topChar != '{') {
return false;
}
}
}
return stack.isEmpty();
}
}
