核心内容摘要
携手龙华油松社区开展“智慧社区”数字技能大讲堂项目
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1输入s “()”输出true示例 2输入s “()[]{}”输出true示例 3输入s “(]”输出false示例 4输入s “([])”输出true示例 5输入s “([)]”输出false这个题目其实是一个阅读理解题示例 5输入s “([)]”输出false这个 示例懂了就行了。
简言之只要遇见右括号然后和栈中栈顶数据比较是一对就返回不是则不对。
即当前右括号对应的左边 必须在栈顶。
public boolean isValid(String s){// 余1 一定是奇数不成对返回falseif(s.length()%
{returnfalse;}MapCharacter, Characterpairsnew HashMapCharacter, Character();pairs.put(),();pairs.put(],[);pairs.put(},{);DequeCharacterstacknew ArrayDeque();for(int i0;is.length();i){char curs.charAt(i);// 如果是左括号则不包含在pairs 的key 中入栈。
// 如果是右括号则包含在pairs 的key 中判断栈是否为空为空返回false否则出栈判断栈顶元素和当前字符是否匹配不匹配返回false匹配则继续循环。
if(pairs.containsKey(cur)){if(!stack.isEmpty()){// 如果栈顶元素门和当前字符锁对应的门匹配则出栈否则返回false final Character popstack.pop();if(pop!pairs.get(cur)){returnfalse;}}else{returnfalse;}}else{stack.push(cur);}}returnstack.isEmpty();}为什么字典Map里要写成 ‘)’ → ‘(’而不是 ‘(’ → ‘)’ 举个例子“([)]”看到(→ 开圆门 → 记在心里入栈看到[→ 开方门 → 记在心里入栈 现在心里记得先开了圆门再开了方门方门是最新的看到)→ 要关圆门了 小明立刻查记忆本“关)门应该对应哪个开门动作”记忆本说( 但他心里记得最近开的是方门[[≠(→ ❌ 配不上游戏失败 关键只有“关门”的时候才需要查“该配哪个开门动作”所以字典必须以“关门动作”为 key❌ 如果反过来写错误方式假如小明的记忆本写成开门动作对应的关门动作()[]那会怎样当他看到(开门他会想“哦以后要关)” —— 但这没用因为他不知道什么时候关也不知道关的时候是否匹配。
当他看到)关门他查不到因为字典里没有以)为 key 的记录。
他就不知道该配哪个开门动作❌ 完全没法判断这个题目很容易理解为只要字符串中存在对应的右括号不要求顺序、不要求连续闭合就算有效” 新题其实变成了检查每种括号的左、右出现次数是否相等。
️ 解法思路新题不需要栈只需要计数器统计 ‘(’ 和 ‘)’ 的数量统计 ‘{’ 和 ‘}’ 的数量统计 ‘[’ 和 ‘]’ 的数量如果每一对的数量都相等就返回 true。
/** * 只要字符串中存在对应的右括号不要求顺序、不要求连续闭合就算有效 */ public boolean isValid2(String s){if(s.length()%