Leetcode之有效的括号
- 2019 年 10 月 4 日
- 筆記
点击上方 毛利学python，选择置顶或星标
第一时间送达Python 技术干货！
我经常逛leetcode，决定每周更新几道leetcode的题目
- 参考极客时间前facebook超哥和前google王争
想购买的找我拿海报
- leetcode大神题解
有效的括号
leetcode 第20题 判断有效的括号
我想到的左右消除，利用字典的对应关系来左括号和右括号相消，如果为空就是真。
class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ stack = [] map = {')':'(',']':'[','}':'{'} for i in s: # 出现了右括号就不添加 if i not in map: stack.append(i) elif not stack or map[i] != stack.pop(): return False return not stack
当然还有堆栈的方法
class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ left = '{[(' rigth = '}])' mylist= [] for i in s: if i in left: mylist.append(i) # 说明就是右括号 # 出现了右括号没有左括号 出现了不对应的左括号，如果有就删到 elif len(mylist) == 0 or left.index(mylist.pop()) != rigth.index(i): return False return len(mylist) == 0
Java代码
class Solution { //3 ms, public boolean isValid(String s) { // 定义一个栈 Stack<Character> stack = new Stack<>(); for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); // || 或 如果是左括号就push if(ch == '(' || ch == '{' || ch == '['){ stack.push(ch); }else{ // 现在是右括号 if(stack.isEmpty()){ return false; } // 定义删除的pop char pop = stack.pop(); // 三种可能 if(ch == ')' && pop != '('){ return false; }else if(ch == '}' && pop != '{'){ return false; }else if(ch == ']' && pop != '['){ return false; } } } return stack.isEmpty(); } }
js
js参考大神的题解
/** * @param {string} s * @return {boolean} */ var isValid = function (s) { //定义一个map var map = { "(": ")", "[": "]", "{": "}" } while (s.length) { var left = s[0]; if (!(left in map)) return false; var i = 1; while (s[i] != map[left] && i < s.length) left = s[i++]; if (s[i] != map[left]) return false s = s.slice(0, i - 1) + s.slice(i + 1, s.length); } return true };
