车身做网站宣传图,阿里巴巴建设电子商务网站目的,花生壳建设网站,深圳网站平台哪家强目录
题解
方法一#xff1a;栈
复杂度分析 题解
方法一#xff1a;栈 判断括号的有效性可以使用「栈」这一数据结构来解决。
我们遍历给定的字符串 s。当我们遇到一个左括号时#xff0c;我们会期望在后续的遍历中#xff0c;有一个相同类型的右括号将其闭合。由于后…目录
题解
方法一栈
复杂度分析 题解
方法一栈 判断括号的有效性可以使用「栈」这一数据结构来解决。
我们遍历给定的字符串 s。当我们遇到一个左括号时我们会期望在后续的遍历中有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时我们需要将一个相同类型的左括号闭合。此时我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型或者栈中并没有左括号那么字符串 s 无效返回 false。为了快速判断括号的类型我们可以使用哈希表存储每一种括号。哈希表的键为右括号值为相同类型的左括号。
在遍历结束后如果栈中没有左括号说明我们将字符串 s 中的所有左括号闭合返回 true否则返回 false。
注意到有效字符串的长度一定为偶数因此如果字符串的长度为奇数我们可以直接返回 false省去后续的遍历判断过程。 C:
class Solution {
public:bool isValid(string s) {int n s.size();if (n % 2 1) {return false;}unordered_mapchar, char pairs {{), (},{], [},{}, {}};stackchar stk;for (char ch: s) {if (pairs.count(ch)) {if (stk.empty() || stk.top() ! pairs[ch]) {return false;}stk.pop();}else {stk.push(ch);}}return stk.empty();}
};
python:
class Solution:def isValid(self, s: str) - bool:if len(s) % 2 1:return Falsepairs {): (,]: [,}: {,}stack list()for ch in s:if ch in pairs:if not stack or stack[-1] ! pairs[ch]:return Falsestack.pop()else:stack.append(ch)return not stack 复杂度分析
时间复杂度O(n)其中 n 是字符串 s 的长度。
空间复杂度O(n∣Σ∣)其中 Σ 表示字符集本题中字符串只包含 6 种括号∣Σ∣6。栈中的字符数量为 O(n)而哈希表使用的空间为 O(∣Σ∣)相加即可得到总空间复杂度。
