算法题-字符串中的有效括号
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true 示例 2：
输入：s = "()[]{}" 输出：true 示例 3：
输入：s = "(]" 输出：false 示例 4：
输入：s = "([)]" 输出：false 示例 5：
输入：s = "{[]}" 输出：true
解题思路1
题目分析
像这种判断有效性的题目往往用栈来操作是非常方便的，我们可以如下的思路分析
创建一个栈Stack和一个Map，Map中存储三个键值对 "()"、"[]"、"{}",键值对都是字符类型
然后我们遍历字符串中的每个字符，拿到字符value，用我们拿到的字符value和栈顶的字符key比较，如果栈顶的字符key对应到Map中的值value1==value，则认为这是一对有效的括号，将栈顶字符出栈。否则将字符value入栈。
一次遍历完成后如果Stack为空，则证明这个字符串是有效的括号。
解题代码
class Solution { public boolean isValid(String s) { if(s.length()==0){ return true; } Map<Character,Character> map = new HashMap();//创建map用于存储键值对 Stack<Character> stack = new Stack();//创建栈用于存储字符串中的字符 map.put('(',')'); map.put('[',']'); map.put('{','}'); for(int i=0;i<s.length();i++){ Character indexChar = s.charAt(i); if(!stack.isEmpty()){ char temp = stack.peek(); Character value = map.get(temp); if(value!=null&&value==indexChar){//如果栈顶字符对应的value不为空且值等于遍历中的item，则栈顶字符出栈 stack.pop(); }else{ stack.push(indexChar);//否则吧正在遍历的父子入栈 } }else{ stack.push(indexChar);//空栈入栈 } } return stack.isEmpty();//如果栈是空的则字符串是合法括号 } } 复制代码解题思路2
这种解题思路意义并不大，不可能在实际应用中被采用，按需观看即可
通过分析我们知道这几个括号(){}[]的ascii字符分别是：40、41、123、125、91、93
因此仍然使用栈的方式解题
每次比较遍历中的字符串的字符c1和栈顶的字符c2的差，如果要保证这两者是一对有效括号则必须满足有 b=c1-c2 ，b的值满足条件b>0且b<3,否则不满足
因为少了Map的构建所以效率可以提升一大截
解题代码
class Solution { public boolean isValid(String s) { //"(){}[]"几个字符asciit的值分别是40、41、123、125、91、93 Stack<Character> stack = new Stack(); for(int i=0;i<s.length();i++){ if(stack.isEmpty()){//如果栈空直接入栈 stack.push(s.charAt(i)); continue; } char indexChar = s.charAt(i);//获取字符串中的字符 Character stackChar = stack.peek();//获取栈顶字符 if(stackChar==null||indexChar==stackChar){//如果栈顶字符为空，或者两个字符相同则遍历的字符串直接入栈 stack.push(indexChar); }else{ int b = indexChar-stackChar; if(b<3&&b>0){//如果遍历的字符与栈顶字符串的差值满足提交则栈顶元素出栈 stack.pop(); }else{ stack.push(indexChar); } } } return stack.isEmpty(); } }
作者：安安安安卓
链接：https://juejin.cn/post/7011802146265890846