問題描述
給定一個只包括 '('逝嚎，')'扁瓢，'{'，'}'补君，'['引几，']' 的字符串，判斷字符串是否有效挽铁。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合伟桅。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串叽掘。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
解答
思路：遍歷字符串楣铁，每遇到一個左括號，則壓入棧中更扁，棧中存儲的是未匹配的左括號盖腕，當遇到一個右括號時，只有棧頂?shù)淖罄ㄌ柛漕愋鸵恢虏拍芷ヅ涑晒Ψ杼叮绻ヅ涑晒棾鰲ｍ斏蘅埃^續(xù)遍歷字符串。最后棧為空時說明字符串是有效的竖哩。
public static boolean solution(String s) {
HashMap<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
char top = stack.empty() ? '*' : stack.pop();
if (top != map.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.empty();
}
下面的方法和上面的思路是一致的，不過做了幾項簡化：使用更簡單的數(shù)據(jù)結(jié)構(gòu)
- 去除HashMap的使用脊僚，括號的類型有限相叁，直接使用多個if即可遵绰。
- 用數(shù)組的索引移動來模擬棧，java中stack的實現(xiàn)是鏈表增淹，預(yù)申請內(nèi)存空間的數(shù)組比一直需要創(chuàng)建節(jié)點對象的鏈表效率要高椿访。而且數(shù)組是基本類型減少了容器對基本類型的包裝和拆箱消耗。
public static boolean solution(String s) {
int S_len=s.length();
if(S_len==0) return true;
char[] stack=new char[S_len];
int top=0;
stack[top++]=s.charAt(0);
for (int i=1;i<S_len;++i){
char x=s.charAt(i);
if (x==')'){
if (top==0)return false;
if (stack[top-1]=='(') {
top--;
continue;
}
return false;
}
if (x==']'){
if (top==0)return false;
if ( stack[top-1]=='[') {
top--;
continue;
}
return false;
}
if (x=='}'){
if (top==0)return false;
if ( stack[top-1]=='{'){
top--;
continue;
}
return false;
}
stack[top++]=x;
}
return top == 0;
}
