C++变位词问题分析
在《编程珠玑》一书的第二章提到了一个变位词问题，变位词指的是一个单词可以通过改变其他单词中字母的顺序来得到，也叫做兄弟单词，如army->mary。由变位词可以引申出几个算法问题，包括字符串包含问题，比较两个字符串是否是变位词，以及找出字典中变位词集合的问题。
一、字符串包含问题
(1) 问题描述：存在字符串1和字符串2，假设字符串2相对较短，如何快速地判定字符串2中的字符都存在于字符串1里（假定字符串只包含字母）？
(2) 举例：字符串1为ABCDEFGHIJK，字符串2为ABCDE，则字符串1包含字符串2，因为字符串2中包含的字母在字符串1中也都有。
(3) 解决方案：
思路一
最直接的思路就是针对字符串2中的每个字符，轮询字符串1进行比较，看是否在字符串1里面。很明显这种的时间效率为O(n*m)。
/*************************************************************************
> File Name: test.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
using namespace std;
void Compare(string long_str, string short_str)
{
int i,j;
for(i=0; i<short_str.size(); ++i)
{
for(j=0; j<long_str.size(); ++j)
{
if(long_str[j] == short_str[i])
{
break;
}
}
if(j == long_str.size())
{
cout << "false" << endl;
return;
}
}
cout << "true" << endl;
return;
}
int main()
{
string l = "ABCDEFGHIJK";
string s = "ABCDEF";
Compare(l, s);
return 0;
}
思路二
这里由于假定了字符串只包含字母，所以我们可以用一个额外的数组flag[26]作为26个字符标识位，先遍历长字符串将对应的标识位置1，再遍历短字符串，如果对应的标示位都是1，则包含；否则不包含。这种方法的时间复杂度为O(n+m)，为了提高空间效率，这里不使用数组而使用26个bit位来作为标示位（bitset容器）。
/*************************************************************************
> File Name: test1.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<bitset>
#include<string>
using namespace std;
bool Compare(string long_str, string short_str)
{
bitset<26> flag;
for(int i=0; i<long_str.size(); ++i)
{
// flag.set(n)置第n位为1
flag.set(long_str[i]-'A');
}
for(int i=0; i<short_str.size(); ++i)
{
// flag.test(n)判断第n位是否为1
if(!flag.test(short_str[i]-'A'))
return false;
}
return true;
}
int main()
{
string l = "ABCDEFGHIJK";
string s = "ABCDEZ";
if(Compare(l, s))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
这种方法还可以进行优化，例如如果长字串的前缀就为短字串，那么我们可以不需要n+m次，而只需要2m次。具体实现请自己思考。
思路三
给每个字母分配一个素数，从2开始到3，5，7...遍历长字串，求得每个字符对应素数的乘积。然后遍历短字串，判断该乘积能否被短字符串中的字符对应的素数整除，如果除的结果存在余数，则说明有不匹配的字母；如果整个过程都没有余数，则说明短字串中的字母在长字串里都有。这种方法的时间复杂度也是O(n+m)，需要26个额外空间存素数，但是这种方法有一个缺点就是需要跟大整数打交道，因为乘积可能非常大。（这里我们使用<cstdint>头文件中定义的int64_t和uint64_t）
/*************************************************************************
> File Name: test2.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
#include<stdint.h>
//#include<cstdint> // C++11
using namespace std;
bool Compare(string long_str, string short_str)
{
unsigned int primeNum[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97,101};
/* int64_t和uint64_t分别表示64位的有符号和无符号整形数 */
/* 在不同位数机器的平台下通用，都是64位 */
uint64_t ch = 1;
for(int i=0; i<long_str.size(); ++i)
{
ch = ch*primeNum[long_str[i]-'A'];
}
for(int i=0; i<short_str.size(); ++i)
{
if(ch%primeNum[short_str[i]-'A'] != 0)
return false;
}
return true;
}
int main()
{
string l = "ABCDEFGHIJK";
string s = "ABCDEK";
if(Compare(l, s))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
二、比较两个字符串是否为变位词
- 上一篇：C++实现矩阵原地转置算法
- 下一篇：C++实现一维向量旋转算法
