题目:
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
提示:
- 1 <= s.length <= 104
- s 仅由括号 '()[]{}' 组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
就利用栈的特点来解题
1.首先判断特殊情况,字符串的长度如果为奇数,那么一定不匹配,直接返回fasle;
2.创建一个栈和创建一个哈希表来存放每一种括号,键为右括号,值为左括号;
3.遍历字符串s:
- 当遇到右括号(键),就去判断右括号在哈希表中所对应的值是否与栈顶的左括号是否一致,如果不一致或者栈中没有左括号,直接返回false,否则,相匹配后,就将已经匹配过的左括号移除。
- 如果遇到左括号,直接压入栈顶。
4.遍历完后,判断栈是否为空,进行返回即可。
代码:
1 class Solution { 2 public boolean isValid(String s) { 3 int n = s.length(); 4 if( n % 2 == 1) return false; 5 Deque<Character> stack = new ArrayDeque<>(); 6 Map<Character,Character> map = new HashMap<Character,Character>(){{ 7 //将)]}作为key 8 put(')','('); 9 put(']','['); 10 put('}','{'); 11 }}; 12 for(int i = 0; i < n; i++){ 13 char c = s.charAt(i); 14 //如果是c是)]} 15 if(map.containsKey(c)){ 16 //map.get(c)为([{ 17 if(stack.isEmpty() || stack.peekLast() != map.get(c)){ 18 return false; 19 } 20 //将栈顶移除,栈顶最接近c的左括号 21 stack.pollLast(); 22 }else{ 23 //如果是c是([{直接入栈 24 stack.addLast(c); 25 } 26 } 27 return stack.isEmpty(); 28 } 29 }标签:map,20,java,示例,力扣,括号,字符串,false,stack From: https://www.cnblogs.com/liu-myu/p/16652642.html