給定一個只包括 '('，')'倔监，'{'直砂，'}'，'['丐枉，']' 的字符串，判斷字符串是否有效掘托。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合瘦锹。
左括號必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
- 思路:
用哈希map將右括號記錄為key鍵
將左括號記錄為value值
第一步如果這個是右括號,并且map里面包含這個鍵,則彈出棧中的左括號來匹配
第二步如果是左括號則壓入棧中
第三步如果匹配完成后,棧中還有數(shù)據(jù)的話,則證明該字符串的符號不匹配,有多余的左括號
via LeetCode官方答案 https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode/
public static boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<>();
Stack<Character> stack = new Stack<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
for (int i = 0; i < s.length(); i++) {
//如果map包含的是鍵,即是右括號,則彈出棧頂元素判斷是否匹配
if (map.containsKey(s.charAt(i))) {
char c = stack.empty() ? '#' : stack.pop(); //用#號來標(biāo)記棧為空,因?yàn)闆]有括號可以和#相匹配
if (c != map.get(s.charAt(i))) //map 通過右括號拿出左括號來做判斷,如果相等則匹配,不等則不匹配
return false;
} else {
stack.push(s.charAt(i));//把左括號壓入棧
}
}
return stack.isEmpty(); // 如果棧內(nèi)還有元素,則證明左括號還有多出來,但沒有右括號匹配了,為空則證明匹配完成
}
