题意概述

• 给定一个仅包含字符'(',')','{','}','['和']',的字符串
• 要求判断给出的字符串是否是合法的括号序列

方法一：字符替换

思路与具体做法

• 如果字符串中有一个连续括号， 就将其删去
• 括号之间是包含关系，如果括号排列合法，则内层连续括号删去后，包含它的外层函数一定也变成连续的，则再重复操作删去即可
• 最后若能全部删去，说明括号排列合法

class Solution {
public:
    bool isValid(string s) {
        while(s.find("()")!=-1||s.find("[]")!=-1||s.find("{}")!=-1){//如果字符串中有连续括号，将其删去 
        	if(s.find("()")!=-1)s.replace(s.find("()"),2,"");
        	if(s.find("[]")!=-1)s.replace(s.find("[]"),2,"");
        	if(s.find("{}")!=-1)s.replace(s.find("{}"),2,"");
		}
		if(!s.size())return true;//全部删完，说明括号排列正确 
		else return false;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2),若字符长度为2n，近似共有n个括号，所以要替换n次，每次替换前查找位置耗时$O\left(n\right)O(n)$O(n) ,所以总的时间复杂度是$O\left(n^2\right)O(n^2)$O(n2)
• 空间复杂度：$O\left(1\right)O(1)$O(1)，未用到额外空间

方法二：栈

思路与具体做法

• 依次遍历，左括号则压入栈，右括号则与栈顶元素做对比即可
• 注意三点
  • 串长非偶数，括号序列不合法
  • 不能配对，括号序列不合法
  • 右括号配对完，仍有左括号剩余，括号序列不合法

class Solution {
public:
    bool isValid(string s) {
		if(s.size()%2)return false;//串长非偶数，括号序列不合法 
		stack<char>ss;
		map<char,char>m;//右括号到左括号的映射 
		m['}']='{';m[']']='[';m[')']='('; 
		for(int i=0;i<s.size();i++){//依次遍历，左括号则压入栈，右括号则与栈顶元素做对比 
			char a=s[i];
			if(a=='('||a=='['||a=='{')ss.push(a);
			else {
				if(!ss.empty()&&ss.top()==m[a])ss.pop();
				else return false;//不能配对，括号序列不合法 
			} 
		}
		return ss.empty();//右括号配对完，仍有左括号剩余，括号序列不合法 		
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，n是字符串长度，要对每个字符进行操作
• 空间复杂度：$O\left(n\right)O(n)$O(n)，最坏情况下均为左括号，字符全部入栈，另外哈希表只建立了常数个映射