题解 | #迷失的括号序列#
迷失的括号序列
http://www.nowcoder.com/practice/e7df3cc4a1534a499dcb1f6553e23799
题意理解
给定一个字符串,由()?组成,?可以代替为(或者),判断能否在替换后,使得字符串变成是括号合法的,若可以则随意输出一种合法的结果。
括号合法的要求:
1.空字符为合法括号序列
2.(+合法括号序列+) 为合法括号序列
3.()+合法括号序列为合法括号序列
方法一
首先,对于基础的括号匹配问题,我们通过以下方法判断其可以匹配:
对于所有i,从1到字符串长度n,考虑字符串前i个字符,如果左括号个数大于等于右括号个数,则前i个字符匹配成功。这里用到一个计数器all,遇到左括号all++,遇到右括号all--,若某时刻all小于0则匹配失败了。
最后i==n时,如果左括号个数等于右括号,即all等于0,则整个字符串匹配成功。
对于该题中存在?的情况,我们可以先计算出还缺少need个左括号,然后将最左边need个?替换为(,其余的?替换为),转化为基础的括号匹配问题。
其中,求出need之后我们可以通过n是否为偶数、左括号的个数是否小于等于n/2,来提前判断该字符串是否能转化为匹配的括号序列。
至于为什么将最左边need个?替换为(。因为左括号越早的出现,该字符串最终匹配的概率越大,而且我们只需要输出一种正确的括号序列即可。这里是贪心的思想。
示意图如下:
具体代码如下:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param brackets string字符串 brackets * @return string字符串 */ string MissingBrackets(string brackets) { int left_count, right_count, n=brackets.size(); for (int i=0;i<n;i++) { if (brackets[i]=='(') left_count++; if (brackets[i]==')') right_count++; } //从括号的个数和字符串的奇偶性判断是否可能。 if (left_count*2>n || right_count*2>n || n%2==1) return "Impossible"; //用need记录还需要几个左括号,而且左括号尽可能更早地出现在左边 int need = n/2-left_count; for (int i=0;i<n;i++) { if (brackets[i]=='?') { if (need>0) { need--; brackets[i]='('; } else brackets[i]=')'; } } //all来判断是否出现了右括号多于左括号的情况 int all=0; for (int i=0;i<n;i++) { if (brackets[i]=='(') all++; if (brackets[i]==')') all--; //注意每次操作后都要判断一下 if (all<0) return "Impossible"; } if (all==0) return brackets; else return "Impossible"; } };
时间复杂度:。所有的循环都是单重循环字符串。
空间复杂度:。仅仅开辟了常数个数的变量。
方法二
(1)对于字符串进行遍历,记录?出现的位置放在数组x中,以及与上一个?之间左括号比右括号多a个,放在数组y中。
(2)对于每个?所在的位置进行判断,如果之前出现的左括号个数(可以加上之前出现的?,假装这些?替换为左括号)大于等于右括号,则暂时匹配成功;否则返回Impossible。注意,这里a是要根据y数组更新的。
(3)最后开始对?进行替换。如果左括号多,则从右往左,先替换为右括号,再依次右括号、左括号得替换;如果右括号多,则对称操作。
具体代码如下:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param brackets string字符串 brackets * @return string字符串 */ vector<int> x,y;//x记录?出现的位置,y记录两个?之间左右括号个数的差 int diff=0, ap=0;//diff记录左括号和右括号的差值 bool judge(int len) { int count = 0, i=0;//count记录?出现的次数。 while(i<len) { diff = diff + y[i];//更新diff if(-diff > count) return false; count++; i++; } if(-diff > x.size() - 1) return false; return true; } string MissingBrackets(string brackets) { // write code here if (brackets.size() % 2) return "Impossible"; int len=brackets.size(); for(int i=0;i<len;i++){ if(brackets[i]=='?'){ x.push_back(i); y.push_back(diff); diff=0; ap++; } else if(brackets[i]==')') diff--; else diff++; } x.push_back(len); y.push_back(diff); len = x.size(); diff = 0; //遍历?的位置,判断把当前?变为左括号时,到此的字符串是否匹配。 if (!judge(len)) return "Impossible"; //最后把?转化为左右括号 if(diff>0){ //左括号多于右括号 diff++; for(int i=len-2;i>=0;i--){ //从最后开始遍历 if(diff>0){ brackets[x[i]]=')'; diff--; } else{ diff++; brackets[x[i]]='('; } } } else{ //右括号多于左括号 diff--; for(int i=0;i<len-1;i++){ //从前开始遍历 if(diff<0){ diff++; brackets[x[i]]='('; } else{ diff--; brackets[x[i]]=')'; } } } return brackets; } };
时间复杂度:。所有的循环都是单重循环字符串。
空间复杂度:。创建了x和y数组用来记录,每个数组的最大长度为字符串的长度。