1.簡述:
描述
給出一個僅包含字元'(',')','{','}','['和']',的字元串,判斷給出的字元串是否是合法的括号序列括号必須以正确的順序關閉,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。
資料範圍:字元串長度
要求:空間複雜度 ,時間複雜度
示例1
輸入:
"()[]{}"
傳回值:
true
示例2
輸入:
"[]"
傳回值:
true
示例3
輸入:
"([)]"
傳回值:
false
import java.util.*;
public class Solution {
public boolean isValid (String s) {
//輔助棧
Stack<Character> st = new Stack<Character>();
//周遊字元串
for(int i = 0; i < s.length(); i++){
//遇到左小括号
if(s.charAt(i) == '(')
//期待遇到右小括号
st.push(')');
//遇到左中括号
else if(s.charAt(i) == '[')
//期待遇到右中括号
st.push(']');
//遇到左打括号
else if(s.charAt(i) == '{')
//期待遇到右打括号
st.push('}');
//必須有左括号的情況下才能遇到右括号
else if(st.isEmpty() || st.pop() != s.charAt(i))
return false;
}
//棧中是否還有元素
return st.isEmpty();
}
}