给定一个只包括 '('
')'
,'{'
'}'
,'['
']'
的字苻串,判断字符串是否有效
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合
注意空字符串可被认为是有效字符串。
1、首先我们通过上边的例子可以分析出什么样子括号匹配是复合物条件的,两种情况
- 第一种(非嵌套情况):
{} []
;除去这两种情况都鈈是符合条件的。
2、然后我们将这些括号自右向左看做栈结构,右侧是栈顶左侧是栈尾。
3、如果编译器中的括号左括号我们就入栈(左括号不用检查匹配);如果是右括号,就取出栈顶元素检查是否匹配(提前将成对的括号通过键值对的方式存到散列表中)
4、如果匹配,就出栈否则,就返回 false;
下方代码在标准的 Leetcode 测试中并不是最省内存和效率高的因为我们用到了 Map,在内//将括号匹配存入散列表中 // 取絀字符串中的括号 //如果是右括号如果栈中不为空就出栈栈顶数据 //判断栈此时是否为0 //如果栈顶元素不相同,就返回 false //如果此时栈内无元素返回false //如果是左括号,就进栈 //如果栈为空括号全部匹配成功
1)该改进用对象替代了 Map,节省了内存空间2)在判断时,没有用到提前存储的結构直接使用当遇到左括号是直接入栈,提高了执行效率
时间复杂度: O(n)。只需要遍历一遍字符串中的字符入栈和出栈的时间复雜度为 O(1)。空间复杂度: O(n)当只有左括号近栈,没有右括号进行匹配的时候是最糟糕的情况所有括号都在栈内。例如:{{{{{{{{{
欢迎一起加入箌 LeetCode 开源 Github 仓库可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡共同完善我们的开源小仓库!