题目来源
20. 有效的括号 - 力扣(LeetCode)
题目描述
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([])"
输出:true
提示:
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
题目限制
要求最优解
不能暴力
思路分析
这题可以用栈这种数据结构来解决,以下是思路提示:
首先,遍历给定的字符串。
当遇到左括号(也就是 '('、'{'、'[' 这几种)的时候,把它们依次压入栈中。因为后续要靠它们来匹配对应的右括号嘛。
而一旦遇到右括号(')'、'}'、'[' )时,就去检查栈顶元素。如果栈为空,那说明没有可以匹配的左括号了,直接返回 false ;要是栈不为空,就看看栈顶的左括号和当前遇到的右括号是不是同一类型的(比如栈顶是 '(',当前是 ')' ,这就是同一类型能匹配上的情况),如果是同一类型,那就把栈顶元素弹出,表示这个括号对匹配上了;要是类型不同,那就不符合要求,直接返回 false 。
最后,当整个字符串都遍历完了,如果栈为空,那就说明所有括号都匹配上了,字符串是有效的,返回 true,要是栈里还有元素,那就意味着有左括号没匹配到右括号,返回 false 。
利用栈来处理的好处在于它能很好地按照顺序来记录和匹配括号,符合括号匹配的先后顺序规则,时间复杂度相对比较优哦。大家可以顺着这个思路再详细去思考具体的实现啦。
具体代码
class Solution {
public:bool isValid(string s) {stack <char> a;for(auto i:s){if(i=='('||i=='{'||i=='[')a.push(i);else {if(a.empty())return false;else{char top=a.top();if((top=='('&&i==')')||(top=='{'&&i=='}')||(top=='['&&i==']'))a.pop();else{return false;}}}}return a.empty();}
};
在上述代码中,我们使用了std::stack
(栈)这个容器来辅助我们解决问题。首先,我们遍历输入的字符串 s
。当遇到左括号('('
、'{'
、'['
)时,我们将其压入栈 a
中。而当遇到右括号时,我们首先检查栈是否为空,如果为空,那就意味着没有对应的左括号来匹配这个右括号,所以直接返回 false
。如果栈不为空,我们获取栈顶元素 top
,然后检查栈顶的左括号和当前的右括号是否是匹配的类型(例如 '('
和 ')'
匹配、'['
和 ']'
匹配、'{'
和 '}'
匹配),如果是匹配的,我们就将栈顶元素弹出,表示这一对括号已经成功匹配;如果不匹配,那么就说明字符串中的括号不是有效的,直接返回 false
。当整个字符串都遍历完后,如果栈为空,那就说明所有的括号都找到了对应的匹配括号,字符串是有效的,返回 true
;否则返回 false
。
这种利用栈来解决括号匹配问题的方法,充分利用了栈的后进先出(LIFO)特性,能够高效且准确地判断字符串中括号的有效性。通过这个问题,我们不仅加深了对栈数据结构的理解,也提升了我们解决实际编程问题的能力。
注意事项
解题思路在编程学习中占据着举足轻重的地位。就拿本题来说,关键在于确定运用何种算法予以攻克。多数人起初往往只会盲目地尝试各种括号匹配方式,然而这毫无成效。若无法洞悉解题的核心思路,个人的编程能力将永远停滞不前。刷题的意义绝非仅仅局限于用代码实现某个题目,更为关键的是要深刻领悟其背后的解题思路,而这其中的核心要素便是算法。它宛如一盏明灯,能够穿透问题的重重迷雾,引导我们找到高效且准确的解决方案,从而在编程的学习之路上实现真正的成长与突破。