<span>最长括号匹配问题</span>
最长括号匹配：
给定字符串，仅包含左括号'('和右括号')'，它可能不是括号匹配的，设计算法找出最长匹配的括号子串，返回该字串的长度。
如：
(() : 2
()() : 4
()(()) : 6
()(())) : 6
(((()())) : 8
1、首先采用栈的存储方式来解决这个问题：
假设起始匹配位置为start = -1，最大匹配长度为MaxLen，考虑第i位字符c：
如果c是左括号，则进行压栈；
如果c为右括号，它一定与栈顶左括号匹配：
（1）如果栈为空，表示没有匹配左括号，start = i，为下一次匹配做准备；
（2）如果栈不空，出栈。再判断栈是否为空，若为空，MaxLen = max（MaxLen，i-start）；若不为空， MaxLen = max（MaxLen，i-栈顶元素位置）；
程序实现：
1 int GetLongestParentheses(const char* p){ 2 int size = (int)strlen(p); 3 stack<int> s; 4 int MaxLen = 0; 5 int start = -1;//左括号的前一个位置 6 for(int i=0;i<size;i++){ 7 if(p[i]=='('){//左括号压栈 8 s.push(i); 9 } 10 else{//为右括号的情况 11 if(s.empty()) 12 start = i; 13 else{ 14 s.pop(); 15 if(s.empty()) 16 MaxLen = max(MaxLen,i-start); 17 else 18 MaxLen = max(MaxLen,i-s.top()); 19 } 20 } 21 } 22 return MaxLen; 23 }
2、采用深度deep表达，将空间复杂度由O(n)降低为O(1).
程序实现：
1 int GetLongestParentheses1(const char* p){ 2 int size = (int)strlen(p); 3 int MaxLen = 0; 4 5 int deep = 0;//遇到了多少左括号 6 int start = -1;//最深第一个左括号的前一个位置 7 for(int i=0;i<size;i++){ 8 if(p[i]=='(') 9 deep++; 10 else{ 11 deep--; 12 if(deep==0){ 13 MaxLen = max(MaxLen,i-start); 14 }else if(deep<0){ 15 deep = 0; 16 start = i; 17 } 18 } 19 } 20 21 deep=0;//遇到了多少右括号 22 start = size;//最深右括号的后一个位置 23 for(int i=size-1;i>=0;i--){ 24 if(p[i]==')') 25 deep++; 26 else{ 27 deep--; 28 if(deep==0) 29 MaxLen = max(MaxLen,start-i); 30 else if(deep<0){ 31 deep = 0; 32 start = i; 33 } 34 } 35 } 36 return MaxLen; 37 }
两者比较且运行结果：
1 #include <iostream> 2 #include <stack> 3 #include <cstring> 4 using namespace std; 5 6 int GetLongestParentheses(const char* p){ 7 int size = (int)strlen(p); 8 stack<int> s; 9 int MaxLen = 0; 10 int start = -1;//左括号的前一个位置 11 for(int i=0;i<size;i++){ 12 if(p[i]=='('){//左括号压栈 13 s.push(i); 14 } 15 else{//为右括号的情况 16 if(s.empty()) 17 start = i; 18 else{ 19 s.pop(); 20 if(s.empty()) 21 MaxLen = max(MaxLen,i-start); 22 else 23 MaxLen = max(MaxLen,i-s.top()); 24 } 25 } 26 } 27 return MaxLen; 28 } 29 30 int GetLongestParentheses1(const char* p){ 31 int size = (int)strlen(p); 32 int MaxLen = 0; 33 34 int deep = 0;//遇到了多少左括号 35 int start = -1;//最深第一个左括号的前一个位置 36 for(int i=0;i<size;i++){ 37 if(p[i]=='(') 38 deep++; 39 else{ 40 deep--; 41 if(deep==0){ 42 MaxLen = max(MaxLen,i-start); 43 }else if(deep<0){ 44 deep = 0; 45 start = i; 46 } 47 } 48 } 49 50 deep=0;//遇到了多少右括号 51 start = size;//最深右括号的后一个位置 52 for(int i=size-1;i>=0;i--){ 53 if(p[i]==')') 54 deep++; 55 else{ 56 deep--; 57 if(deep==0) 58 MaxLen = max(MaxLen,start-i); 59 else if(deep<0){ 60 deep = 0; 61 start = i; 62 } 63 } 64 } 65 return MaxLen; 66 } 67 int main() 68 { 69 char str1[] = "(()"; 70 char str2[] = "()()"; 71 char str3[] = "()(())"; 72 char str4[] = "()(()))"; 73 char str5[] = "(((()()))"; 74 cout<<GetLongestParentheses(str1)<<endl; 75 cout<<GetLongestParentheses(str2)<<endl; 76 cout<<GetLongestParentheses(str3)<<endl; 77 cout<<GetLongestParentheses(str4)<<endl; 78 cout<<GetLongestParentheses(str5)<<endl; 79 cout<<"----------------deep O(1)--------------------"<<endl; 80 cout<<GetLongestParentheses1(str1)<<endl; 81 cout<<GetLongestParentheses1(str2)<<endl; 82 cout<<GetLongestParentheses1(str3)<<endl; 83 cout<<GetLongestParentheses1(str4)<<endl; 84 cout<<GetLongestParentheses1(str5)<<endl; 85 return 0; 86 }
转载请注明出处：
C++博客园：godfrey_88
投递谷歌等公司10个岗位 >
查看10道真题和解析