点击上方 毛利学python,选择置顶或星标
第一时间送达Python 技术干货!
我经常逛leetcode,决定每周更新几道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
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参考大神的题解
/**
* @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
};