給定一個只包括 '('诫龙，')'析显，'{'，'}'签赃，'['谷异，']' 的字符串，判斷字符串是否有效姊舵。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合晰绎。
左括號必須以正確的順序閉合寓落。
注意空字符串可被認(rèn)為是有效字符串括丁。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
- 思路:
利用棧來解決問題,當(dāng)碰到左括號的,壓入棧,當(dāng)碰到右括號時,就要開始彈出棧頂?shù)淖罄ㄌ?那么第一步要判斷此時的棧是否為空,因為棧為空時,就證明無左括號壓入棧,第二步根據(jù)各個右括號,依次彈出棧頂元素,判斷是否為一對,第三步匹配完成后,要判斷棧內(nèi)是否還有元素,如果有元素的話,就證明左括號還有多,而右括號已經(jīng)匹配完了. - 還有一個問題就是,一開始就要判斷輸入的字符串長度是否為偶數(shù),因為符號是兩兩搭配的,如果為奇數(shù),則直接就可以判斷為false
public static boolean isValid(String s) {
LinkedList<String> list = new LinkedList<>();
int length = s.length();
if (length % 2 != 0)
return false;
for (int i = 0; i < length; i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
list.push(s.charAt(i) + "");
} else if (list.isEmpty()) {
return false;
} else if (s.charAt(i) == ')') {
String pop = list.pop();
if (!pop.equals("("))
return false;
} else if (s.charAt(i) == ']') {
String pop = list.pop();
if (!pop.equals("["))
return false;
} else if (s.charAt(i) == '}') {
String pop = list.pop();
if (!pop.equals("{"))
return false;
}
}
if (!list.isEmpty())
return false;
return true;
}
