069有效的括号

有效的括号题目链接https://leetcode.cn/problems/valid-parentheses/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答//方法栈 //时间复杂度O(n) //空间复杂度O(n) public boolean isValid(String s) { int n s.length(); int[] stack new int[n]; int top -1; for(int i0; in; i){ if(s.charAt(i) ( || s.charAt(i) { || s.charAt(i) [){ stack[top] s.charAt(i); } else if(top 0 ((s.charAt(i) ) stack[top] () || (s.charAt(i) } stack[top] {) || (s.charAt(i) ] stack[top] [))){ top--; } else{ return false; } } return top -1; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路利用栈判断是否为有小括号当遍历到的字符是左括号时直接入栈当遍历到的字符为右括号时判断当前栈顶的左括号是否与当前遍历到的右括号是一对若不是则证明不是有效字符若是则出栈一个字符知道遍历完s的所有字符最后判断栈是否为空即可。看了官方题解后的解答//方法栈 //时间复杂度O(n) //空间复杂度O(n∣Σ∣)其中 Σ 表示字符集本题中字符串只包含 6 种括号∣Σ∣6 public boolean isValid(String s) { int n s.length(); //若能匹配那么字符串的长度一定为偶数 if(n%2 1){ return false; } DequeCharacter stack new LinkedList(); //key右括号 value左括号 MapCharacter, Character map new HashMap(); map.put(),(); map.put(},{); map.put(],[); for(int i0; in; i){ char ch s.charAt(i); // 当前字符为右括号 if(map.containsKey(ch)){ if(stack.isEmpty() || stack.peek() ! map.get(ch)){ return false; } stack.pop(); } //当前字符为左括号 else{ stack.push(ch); } } return stack.isEmpty(); }分析​ 1、官方题解的思路与我的思路大体一致只是进行了部分优化优化的点在于​ 第一官方题解在遍历前先对字符串的长度进行判断若字符串的长度为奇数则证明一定不可以完全匹配直接返回答案从而跳过后续遍历判断的步骤​ 第二官方题解利用哈希表映射了右括号与左括号的对应关系巧妙设计让右括号作为key让左括号作为value每当遍历到一个字符的时候只需判断哈希表中是否存在这个键就可以判断当前字符是左括号还是右括号若是右括号在判断栈顶元素是否是与之匹配的左括号时直接从哈希表中获取对应的右括号再将其与栈顶元素进行比较即可。这样做让代码的可扩展性更强而不用在判断时一个个的列举条件。总结本题主要考察栈和哈希表思路简单但是可以从代码的扩展性上进行优化。