leetcode问题是:
给定仅包含字符"("、"("、"{"、"}"、"["one_answers"]"的字符串s,请确定输入字符串是否有效。
输入字符串在以下情况下有效:
打开的括号必须由相同类型的括号闭合。打开的支架必须按正确顺序关闭。
我的代码:
class Solution:
def isValid(self, s: str) -> bool:
mapper = {')':'(',
']':'[',
'}':'{'}
stack = []
top_element = -1
if not s:
return False
for char in s:
if char in mapper and top_element == -1:
return False
if char in mapper and mapper[char] == top_element:
stack.pop()
else:
stack.append(char)
top_element = stack[-1]
return not stack
该逻辑适用于"(("输入,但不适用于"{[]}"。我认为错误在if-else
条件中
我做错了什么?
有几件事:
class Solution:
def isValid(self, s: str) -> bool:
^^^^
- 这个函数需要是非静态的吗
mapper = {')':'(',
']':'[',
'}':'{'}
stack = []
top_element = -1
if not s:
return False
for char in s:
if char in mapper and top_element == -1:
return False
if char in mapper and mapper[char] == top_element:
stack.pop()
# Change top element
top_element = stack[-1] if stack else -1
您需要在
pop
之后更改top_element
。如果括号正在闭合,但与
top_element
不匹配,该怎么办?
elif char in mapper and mapper[char] != top_element:
return False
else:
stack.append(char)
top_element = stack[-1]
return not stack
此外,您还可以检查s
是否包含括号以外的其他符号,以防万一。
逻辑和代码都很好,只需要在弹出后更新topelement。(更改此项:
if char in mapper and mapper[char] == top_element:
stack.pop()
else:
stack.append(char)
top_element = stack[-1] if len(stack)>0 else None
对此(再加一行评论(:
if char in mapper and mapper[char] == top_element:
stack.pop()
top_element = stack[-1] #additional line
else:
stack.append(char)
top_element = stack[-1]
var isValid = function(s) {
const stack = [];
const brackets = {
'{':'}',
'[':']',
'(':')'
}
const closing = Object.values(brackets);
for (let ch of s) {
if (brackets[ch]) {
stack.push(brackets[ch]);
} else if (ch == stack.at(-1)) {
stack.pop()
} else if (closing.includes(ch)) {
return false;
}
}
return !stack.length;
};
console.log(isValid("{([])}")); // true
console.log(isValid("]")); // false
在Leetcode上使用JavaScript格式尝试此代码,您将通过。。
- 你走的是正确的道路
- 我们可以简单地在初始化时向堆栈添加一个sentinel值
- 这将通过:
class Solution:
def isValid(self, base_string):
memo = {')': '(', '}': '{', ']': '['}
stack = [0]
for character in base_string:
if character in memo:
if stack.pop() != memo[character]:
return False
else:
stack.append(character)
return stack == [0]