一道Google top coder的850分例题及解答
陈硕∗
2006年4月
原题：
假设有这样一种字符串，它们的长度不大于26，而且若一个这样的字符串其长度为m，则这个字符串必定由a,b,c,...,z中的前m个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为5，那么它一定是由a,b,c,d,e这5个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
现在我们用一个由大写字母A和B构成的序列来描述这类字符串里各个字母的前后顺序：
•如果字母b在字母a的后面，那么序列的第一个字母就是A（After），否则序列的第一个字母就是B（Before）；
•如果字母c在字母b的后面，那么序列的第二个字母就是A，否则就是B；
•如果字母d在字母c的后面，那么……不用多说了吧？直到这个字符串的结束。
这规则甚是简单，不过有个问题就是同一个AB序列，可能有多个字符串都与之相符，比方说序列"ABA"，就有"acdb"、"cadb"等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的AB序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。
注：如果结果大于10亿就返回-1。
我的最终解答（没有考虑溢出的情况）：
Code1:O(N2)
//the best way
//O(N^2)
int countABbest(const string&AB)
{
assert(AB.find_first_not_of("AB")==string::npos);
vector<int>current,next;//should we reserve these vectors?
current.push_back(1);
for(string::const_iterator letter=AB.begin();
letter!=AB.end();++letter){
∗email:giantchen@gmail,homepage:www.chenshuo
1
next[0]=0;//in fact,we could set the entire vector to zero
if(*letter==’A’){
partial_sum(current.begin(),d(),next.begin()+1);
}else{
partial_sum(current.rbegin(),d(),next.begin()+1);
reverse(next.begin(),d());
}
swap(current,next);
}
return accumulate(current.begin(),d(),0);
}
int main()
{
const char*AB="ABBAAB";
printf("’%s’:%d\n",AB,countABbest(AB));
}
Code1:O(N2)
下面谈一谈我在解决这个问题时的思路。
1.初步分析
以下“字符串”特指题目中提到的由小写字母a,b,c等等组成的字符串，每个字母出现且仅出现一次。显然题目要求我们写一个函数f，f的输入是一个长度为n的AB序列w，w代表了一个字符串集合s（集合中的元素都是长度为m(m=n+1)的字符串），f的返回值是这个集合的元素个数|s|，即|s|=f(w)。用高中学过的一点排列组合知识，可分析知：
1.长度为m的字符串有m!个（’!’表示阶乘）因为这相当于m个不同字母的全排列；
2.长度为n的AB序列有2n个因为每个位置有2种可能，一共有n个位置；
3.由于2n≤m!(m=n+1)，所以AB序列的数目不大于字符串的数目。
4.每个字符串刚好有一个AB序列与之对应。比如对于字符串"abdec"，我们很容易得知b在
a后，c在b后，d在c前，e在d后，因此它对应的AB序列为"AABA"。可见拿到一个字符串，立刻就能求出它对应的那一个AB序列。
5.每个AB序列至少对应一个字符串（当然也对应多个，因为字符串数目远远大于AB序列数
目）。比如任取一个AB序列"ABA"，很容易构造出与它对应的字符串：
i.b在a后，得"ab"；
ii.c在b前，得"acb"或"cab"；
iii.d在c后，拿"acb"来说，可得"acdb"和"acbd"；拿"cab"来说，可得"cdab"，"cadb"
和"cabd"；这样一共构造了5个与"ABA"对应的字符串，而且不会再有别的字符串
了（why?）。
其实我们已经到了蛮力解决问题的办法。
6.根据4、5，得知如果穷举出长度为n的AB序列（共2n个），并计算每个序列对应的字符串
数目，那么把所有这些数目加起来，应该等于(n+1)!，这可以用作我们算法的一个检验。
7.其实这可以看作集合的划分，把一个有m!个元素的集合U划分为2n个不相交的子集
S0,S1,...,S2n−1，每个子集S i是一个类别，每个字符串都属于一个类别，问题转变为求给定类别中有多少个元素。
2
2.蛮力解决
在想到前面的分析之前，我先用一种蛮力办法部分地解决了这个问题，思路是拿到一个长度为n的AB序列，穷举所有长度为n+1的字符串，遇到匹配的就记录下来。这样得到第一个程序，这个程序虽然效率极低，但可以用来检验后面程序的正确性，是个标竿。
Code2:O(N!·N2)
//if AB maches str
bool match(const string&AB,const string&str)
{
/
/many ways to improve this function,but we won’t bother it.
for(size_t i=0;i<AB.length();++i){
size_t first=str.find(’a’+i);
size_t second=str.find(’a’+i+1);
assert(first!=string::npos&&second!=string::npos);
if(AB[i]==’A’&&first>second){
return false;
}else if(AB[i]==’B’&&first<second){
return false;
}
}
return true;
}
//the stupid way
//O(N!*N^2)
int countAB(const string&AB)
{
assert(AB.find_first_not_of("AB")==string::npos);
string str;
int count=0;
int m=(int)AB.length()+1;
//construct the initial string
for(int i=0;i<m;++i){
str.push_back(’a’+i);
}
do{
if(match(AB,str)){
printf("%s,",str.c_str());
count++;
}
}while(next_permutation(str.begin(),d()));
return count;
}
Code2:O(N!·N2)
上面这个程序是以AB序列为中心，想办法到与它匹配的字符串。为了看它能否通过第6点分析的检验，我写了一个enumAB(int n)函数，用来穷举长度为n的所有AB序列，并做检验（检验基本靠眼）。
Code3
void enumAB(int n)
{
assert(0<=n&&n<26);
int nAB=1<<n;
3
int total=0;
for(int i=0;i<nAB;++i){
string AB;
for(int bit=n-1;bit>=0;--bit){
if(i&(1<<bit)){
AB.push_back(’B’);
}else{
AB.push_back(’A’);
}
字符串长度的正确表示}
int count=countAB(AB);
total+=count;
printf("%s:%d\n",AB.c_str(),count);
}
printf("\nTotal strings:%d\n",total);
}
Code3
以下是enumAB(4)的运行结果（5!=120，初步检验通过）：
enumAB(4)
AAAA:1
AAAB:4
AABA:9
AABB:6
ABAA:9
ABAB:16
ABBA:11
ABBB:4
BAAA:4
BAAB:11
BABA:16
BABB:9
BBAA:6
BBAB:9
BBBA:4
BBBB:1
Total strings:120
enumAB(4)
如果想穷举所有AB序列和它们对应的字符串，还可以用一种效率稍高的蛮力算法：以字符串为中心，穷举所有长度为m的字符串，把它归入相应的AB序列名下。代码如下。
Code4
getAB(const string&str)
{
const char*alphabet="abcdefghijklmnopqrstuvwxyz";
assert(str.find_first_not_of(alphabet,0,str.length())==string::npos);
int pos[26]={0};
char AB[26]={0};
int m=(int)str.length();
for(int i=0;i<m;++i){
pos[str[i]-’a’]=i;
}
for(int i=0;i<m-1;++i){
4
AB[i]=pos[i]<pos[i+1]?’A’:’B’;
}
return AB;//we are not return the local char array,but a string object.
}
void enumStr(int m)
{
string str;
int nAB=0;
for(int i=0;i<m;++i){
str.push_back(char(’a’+i));
}
map<string,vector<string>>AB2strs;
do{
string AB=getAB(str);
//printf("%s is of%s\n",str.c_str(),AB.c_str());
AB2strs[AB].push_back(str);
}while(next_permutation(str.begin(),d()));
for(map<string,vector<string>>::iterator it=AB2strs.begin();
it!=d();++it){
++nAB;
printf("%s(%d):",it->first.c_str(),it->second.size());
for(vector<string>::iterator str=it->second.begin();
str!=it-&d();++str){
printf("%s,",str->c_str());
}
printf("\n");
}
printf("\nTotal ABs:%d\n",nAB);
}
Code4
以下是enumStr(4)的运行结果（23=8，初步检验通过）：
enumStr(4)
AAA(1):abcd,
AAB(3):abdc,adbc,dabc,
ABA(5):acbd,acdb,cabd,cadb,cdab,
ABB(3):adcb,dacb,dcab,
BAA(3):bacd,bcad,bcda,
BAB(5):badc,bdac,bdca,dbac,dbca,
BBA(3):cbad,cbda,cdba,
BBB(1):dcba,
Total ABs:8
enumStr(4)
3.进阶分析
我们也可以根据前面第5点分析，做出一个更高效的蛮力算法，不过蛮力毕竟是蛮力，还是让我们动动脑筋，做个真正高效的算法吧。
我第一次拿到这个问题时，先用蛮力算法打印出前面的结果，试图分析其规律，没成功。便又在纸上演算了了一阵，发现其实可以递推解决（当然也可以递归解决），以下内容最好在纸上演算。比如对于AB序列"AAA"，字母d只可能在第3号位置出现一次（"abcd"）；递推一下，
5
对于序列"AAAB"，e 在d 前，那么e 可以在第0,1,2,3号位置各出现一次（"eabcd","aebcd","abecd","abced"）。
又比如根据以前面第5点分析，如果我们知道对于序列"AB"，字母c 可能在第0号位置出现一次（"cab"）、在第1号位置出现一次（acb ）；那么对于序列"ABA"，字母d 会在第1,2,3号位置分别出现1,
2,2次，因此"ABA"对应的字符串共有5个；同理对于序列"ABB"，字母d 会在第0,1号位置分别出现2,1次，因此"ABB"对应的字符串共有3个。
继续递推，对于序列"ABBA"，e 在d 后，那么e 可以在第1,2,3,4号位置分别出现2,3,3,3次（具体说来，对于d 在第0号位置出现的那2次，那么e 可以在第1,2,3,4号位置各出现2次；d 在第1号位置出现1次，那么e 可以在第2,3,4号位置各出现1次，对位加起来就得到前面"2,3,3,3"的结果），因此"ABBA"对应的字符串共有11个。
到这里，我们已经发现递推的规律了：对于AB 序列w ，用二维数组occurs[][]表示第letter 个字母在位置pos 出现的次数occurs[letter ][pos ]（这个说法不太严格，应该说是w 的前面长度为letter 的子序列对应的字符串中，最大那个字母出现的位置和次数，呵呵，还是比较绕口）。如果字母p 在位置q 1出现n 1次（occurs[p ][q 1]=n 1），而AB 序列的当前元素为’A’，那么字母p +1会在位置q 1+1,q 1+2,...,p 各出现n 1次；如果AB 序列的当前元素为’B’，那么字母p +1会在位置0,1,...,q 1各出现n 1次；如果字母p 还在q 2位置出现了n 2次（occurs[p ][q 2]=n 2），那么对于’A’情况，字母p +1还会在位置q 2+1,q 2+2,...,p 各出现n 2次；那么对于’B’情况，字母p +1还会在位置0,1,...,q 2各出现n 2次。需要把这些情况都累加起来。
对于序列"ABBAA"，递推表如下：
位置q
p AB 字符012345说明
1’A’0,1,0,0,0,0字母b 在位置1出现1次
2’B’1,1,0,0,0,0字母c 在位置0、1分别出现1次
3’B’2,1,0,0,0,0字母d 在位置0、1分别出现2、1次
4’A’0,2,3,3,3,0字母e 在位置1、2、3、4分别出现2、3、3、3次
5’A’0,0,2,5,8,11字母f 在位置2、3、4、5分别出现2、5、8、11次
可知对应的字符串有26个。如果细心，已经能发现递推中的部分和(partial sum)关系。即对于’A’情况，occurs[p +1][q ]= q −1i =0occurs[p ][i ]；即对于’B’情况，occurs[p +1][q ]= p
i =q occurs[p ][i ]；
4.解决
既然递推关系有了，很容易就能写出代码。这个算法的复杂度是O (N 3)。
Code 5:O (N 3)
//the better way
//O(N^3)
int countABbetter(const string&AB)
{
assert(AB.find_first_not_of("AB")==string::npos);
int n =(int)AB.length();
int m =n +1;
//’letter’at ’pos’occurs ’occurs[letter][pos]’times.
vector<vector<int>>occurs(m,vector<int>(m,0));6

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。