問題：
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
大意：
給出一個只包含 '(', ')', '{', '}', '[' 和 ']' 的字符串荐糜，判斷它的輸入是否是有效的。
括號必須是以正確的順序關閉的疲陕， "()" 和 "()[]{}" 都是有效的郑叠，但是 "(]" 和 "([)]" 是無效的胚宦。
思路：
題目的要求說來也簡單，就是判斷括號是不是有效的瘾带，自己先用測試用例試了一下沟堡，括號中包含括號也是有效的。
其實無效的情況也就幾種介评，左括號匹配到了不一樣的右括號库北、左括號多了、右括號多了们陆，我用一個數(shù)組記錄不同位置出現(xiàn)的括號的種類寒瓦，出現(xiàn)新的右括號的時候判斷是否匹配到了正確的括號，還要看是不是是多了的右括號坪仇，最后看有沒有多出來的左括號杂腰。方法很笨，代碼也寫的很冗余椅文，不過速度還可以喂很。
代碼（Java）：
public class Solution {
public boolean isValid(String s) {
int[] markArr = new int[s.length()];// 1表示()，2表示[]皆刺，3表示{}
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '(') {
markArr[i] = 1;
} else if (arr[i] == ')') {
boolean hasMatched = false;
for (int j = i-1; j >= 0; j--) {
if (markArr[j] > 0 && markArr[j] != 1) return false;
else if (markArr[j] == 1) {
markArr[j] = 0;
hasMatched = true;
break;
}
}
if (!hasMatched) return false;
} else if (arr[i] == '[') {
markArr[i] = 2;
} else if (arr[i] == ']') {
boolean hasMatched = false;
for (int j = i-1; j >= 0; j--) {
if (markArr[j] > 0 && markArr[j] != 2) return false;
else if (markArr[j] == 2) {
markArr[j] = 0;
hasMatched = true;
break;
}
}
if (!hasMatched) return false;
} else if (arr[i] == '{') {
markArr[i] = 3;
} else if (arr[i] == '}') {
boolean hasMatched = false;
for (int j = i-1; j >= 0; j--) {
if (markArr[j] > 0 && markArr[j] != 3) return false;
else if (markArr[j] == 3) {
markArr[j] = 0;
hasMatched = true;
break;
}
}
if (!hasMatched) return false;
}
}
for (int i = 0; i < markArr.length; i++) {
if (markArr[i] > 0) return false;
}
return true;
}
}
他山之石：
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
// Iterate through string until empty
for(int i = 0; i<s.length(); i++) {
// Push any open parentheses onto stack
if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
stack.push(s.charAt(i));
// Check stack for corresponding closing parentheses, false if not valid
else if(s.charAt(i) == ')' && !stack.empty() && stack.peek() == '(')
stack.pop();
else if(s.charAt(i) == ']' && !stack.empty() && stack.peek() == '[')
stack.pop();
else if(s.charAt(i) == '}' && !stack.empty() && stack.peek() == '{')
stack.pop();
else
return false;
}
// return true if no open parentheses left in stack
return stack.empty();
}
}
這個做法用到了Stack棧這個類型少辣，確實這道題很適合用棧來做，先進后出羡蛾，遇到左括號的時候放進去漓帅，遇到右括號的時候從棧頂拿括號進行匹配，匹配失敗就錯了林说，全部匹配正確而且最后棧里沒東西了就對了煎殷。代碼簡潔多了。
合集：https://github.com/Cloudox/LeetCode-Record
