数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究检查表达式中括号是否平衡 - O(1) 空间 - O(N^2) 时间复杂度（C++）
概念
给定一个包含字符 ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ 和 ‘]’ 的字符串 str，任务是判断括号是否平衡。
括号被认为是平衡的，如果：
打开的括号必须由相同类型的括号关闭。
并且打开的括号必须按照正确的顺序关闭。
输入 − str = “(()){}”
输出 − 是
输入 − str = “))(([][”
输出 − 否
方法
分配两个变量 a 和 b 来跟踪要比较的两个括号。
需要维护一个计数器，当遇到开括号时其值递增，当遇到闭括号时其值递减。
当遇到开括号时，将 b = a，a = a + 1 以及 count=count+1。
当遇到闭括号时，递减 count 并比较 i 和 j 处的括号，
如果发现 a 和 b 处的括号匹配，则将字符串中 a 和 b 位置的字符替换为 ‘#’。a 自增，b 自减，直到遇到非 ‘#’ 值或 b ≥ 0。
如果发现 a 和 b 处的括号不匹配，则返回 false。
如果 count != 0，则返回 false。
示例
// C++ implementation of the approach
#include <iostream>
using namespace std;
bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
count1--;
if (j1 > -1 && s1[j1] == tocom1) {
s1[i1] = '#';
s1[j1] = '#';
while (j1 >= 0 && s1[j1] == '#')
j1--;
i1++;
return 1;
}
else
return 0;
}
bool isValid(string s1){
if (s1.length() == 0)
return true;
else {
int i1 = 0;
int count1 = 0;
int j1 = -1;
bool result1;
while (i1 < s1.length()) {
switch (s1[i1]) {
case '}':
result1 = helperFunc(count1, s1, i1, j1, '{');
if (result1 == 0) {
return false;
}
break;
case ')':
result1 = helperFunc(count1, s1, i1, j1, '(');
if (result1 == 0) {
return false;
}
break;
case ']':
result1 = helperFunc(count1, s1, i1, j1, '[');
if (result1 == 0) {
return false;
}
break;
default:
j1 = i1;
i1++;
count1++;
}
}
if (count1 != 0)
return false;
return true;
}
}
// Driver code
int main(){
string str1 = "[[]][]()";
if (isValid(str1))
cout << "Yes";
else
cout << "No";
return 0;
}输出
Yes
更新于: 2020年7月23日
311 次浏览
广告