使用STL解决变位词有关问题

使用STL解决变位词问题

**抛出问题**

这是一个算法题目，详细要求如下：

?

输入N和一个要查找的字符串，以下有N个字符串，我们需要找出其中的所有待查找字符串的变位词（例如eat,eta,aet就是变位词）按字典序列输出，并且输出总数目

第一行：N(代表共有N个字符串属于被查找字符串) （N<=50） 第二行：待查找的字符串(不大于10个字符) 以下N行：被查找字符串（不大于10个字符）

按字典序列输出在被查找字符串中待查找字符串的所有变位词 每行输出一个 输出完成后输出总数目

Sample Input

7asdfgasdgfasdfgdsafgxcvcvgfdsatyuvasd

Sample Output

asdfgasdgfdsafggfdsa4

解题思路：

?

1、判断是否为变位词

?

2、将变位词按字典顺序输出

?

解题步骤：

?

1、定义string

?

2、判断两个string是否为变位词

?

3、将是变位词的string放入vector<string>中

?

4、vector进行sort排序

?

5、统计vector中的size

?

6、输出

?

编码：

?

1、判断两个string是否为变位词

（1）将两个string进行sort排序

（2）判断排序后的string是否相同：如果相同，则两个string为变位词；反之，则不同

?

int isbianweici(string s,string s1){sort(s.begin(),s.end());sort(s1.begin(),s1.end());if(s == s1)return 1;elsereturn 0;}

?

?2、将vector<string>sort排序，输出

?

sort(sreslut.begin(),sreslut.end());for(it=sreslut.begin();it != sreslut.end();it ++)cout<<*it<<endl;cout<<sreslut.size()<<endl;

?

?

完整代码：

?

#include<string>#include<vector>#include<string>#include<iostream>#include<algorithm>using namespace std;int isbianweici(string s,string s1){sort(s.begin(),s.end());sort(s1.begin(),s1.end());if(s == s1)return 1;elsereturn 0;}int main(){int n;cin>>n;string firsts;cin>>firsts;vector<string> sreslut;vector<string>::iterator it;for(int i=0;i<n;i++){string ss;cin>>ss;if(isbianweici(firsts,ss))sreslut.push_back(ss);}sort(sreslut.begin(),sreslut.end());for(it=sreslut.begin();it != sreslut.end();it ++)cout<<*it<<endl;cout<<sreslut.size()<<endl;}

?

?

总结：

?

1、短短只有35行代码；

?

2、在查找变位词的策略上，如果采用先将string的所有变位词找出放入vector<string>中，然后在进行对比的方式，在算法运行中，如果string的长度为n，则需要进行n！次排序以查找string所有的变位词，这种方式在算法复杂度上显示是不能接受的；

?

3、在STL中，string类型的sort排序，会将string中的每一个char按照字典顺序进行排序，如果两个string经过sort排序之后，是相同的，那这两个string必然是变位词（两个string不同）；

?

4、在STL中，vector<string>的sort排序，同样会将vector<string>中的元素按照字典顺序进行排序。

?

5、问题在35行代码之后，迎刃而解。

?

后话：

?

第一次写博客，最近初学STL，代码编写没有完全按照编程规范，有待学习。希望各位指点交流。