字符串问题

与字符串相关的问题在各大互联网公司的笔试和面试中出现的频率极高。例如，网上广为流传的一道单词翻转题：输入“I am a student.”，要求输出“student. a am I”。

本章重点介绍6个典型的字符串问题，分别是字符串的旋转、字符串的包含、字符串的全排列、字符串转换成整数、回文判断、最长回文子串。这6个问题中，除了“将字符串转换成整数”这个问题需要特别注意细节之外，其他5个问题都有多种思路和多种解法，比如先从蛮力解法入手，然后考虑是否能逐步优化。

读完本章后读者会发现，好的思路都是在充分考虑到问题本身的特征的前提下，或巧用合适的数据结构，或选择合适的算法降低时间复杂度，或选用效率更高的算法。

1.1　字符串的旋转

题目描述

给定一个字符串，要求将字符串前面的若干个字符移到字符串的尾部。例如，将字符串"abcdef"的前3个字符'a'、'b'和'c'移到字符串的尾部，那么原字符串将变成"defabc"。请写一个函数实现此功能。

分析与解法

解法一：蛮力移位

初看此题，可能最先想到的方法是将需要移动的字符一个一个地移到字符串的尾部。

如果定义指向该字符串的一个指针s，然后设该字符串的长度为n，那么，可以先编写一个函数LeftShiftOne (char* s, int n)，以完成将一个字符移到字符串尾部的功能：

void LeftShiftOne(char* s, int n)
{
 　　// 保存第一个字符
 　　char t = s[0];
 　　for (int i = 1; i < n; i++)
 　　{
 　　　　s[i - 1] = s[i];
 　　}
 　　s[n - 1] = t;
}

然后再调用m次LeftShiftOne函数，使得字符串开头的m个字符移到字符串的尾部：

void LeftRotateString(char* s, int n, int m)
{
 　　while (m--)
 　　{
 　　　　LeftShiftOne(s, n);
 　　}
}

这样就完成了将若干个字符移到字符串尾部的要求。

下面来分析一下这种方法的时间复杂度和空间复杂度。针对长度为n的字符串来说，假设需要移动m个字符到字符串的尾部，那么总共需要m×n次操作。同时设立一个变量保存第一个字符。因此，时间复杂度为O (mn)，空间复杂度为O (1)。

有没有更好的办法来降低时间复杂度呢？

解法二：三步反转

对于这个问题，换一个角度思考一下。既然题目要求将字符串前面的那部分原封不动地移到字符串的尾部，那么是否可以把需要移动的部分跟不需要移动的部分分开处理呢？例如，可以先将一个字符串分割成两个部分，然后将这两个部分的字符串分别反转，最后再对整个字符串进行整体反转，即可解决字符串旋转的问题。

拿题目中的例子来说，给定字符串"abcdef"，若要将"def"移动到"abc"的前面，只需要按照下述3个步骤操作即可。

（1）将原字符串分为X和Y两个部分，其中X为"abc"，Y为"def"。

（2）将X的所有字符反转，即相当于反转"abc"得到"cba"；再将Y的所有字符也反转，即相当于反转"def"得到"fed"。

（3）最后，将上述步骤得到的结果再给予整体反转，即整体反转"cbafed"得到"defabc"，这样，就实现了字符串的反转。

参考代码如下：

void ReverseString(char* s, int from, int to)
{
 　　while (from < to)
 　　{
 　　　　char t = s[from];
 　　　　s[from++] = s[to];
 　　　　s[to--] = t;
 　　}
}
void LeftRotateString(char* s, int n, int m)
{
 　　// 若要左移动大于n位，那么与%n是等价的
 　　m %= n;
 　　ReverseString(s, 0, m - 1);
 　　ReverseString(s, m, n - 1);
 　　ReverseString(s, 0, n - 1);
}

这种把字符串先分为两个部分，各自反转，最后整体反转的方法，俗称“三步反转”法，其时间复杂度为O(n)，空间复杂度为O(1)。

举一反三

单词翻转

输入一个英文句子，翻转句子中单词的顺序。要求单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，若输入“I am a student.”，则输出“student. a am I”。

1.2　字符串的包含

题目描述

给定一长字符串a和一短字符串b。请问，如何最快地判断出短字符串b中的所有字符是否都在长字符串a中？请编写函数boolStringContain(string &a, string &b)实现此功能。

为简单起见，假设输入的字符串只包含大写英文字母。下面举几个例子。

• 如果字符串a是"ABCD"，字符串b是"BAD"，答案是true，因为字符串b中的字母都在字符串a中，或者说b是a的真子集。
• 如果字符串a是"ABCD"，字符串b是"BCE"，答案是false，因为字符串b中的字母E不在字符串a中。
• 如果字符串a是"ABCD"，字符串b是"AA"，答案是true，因为字符串b中的字母A包含在字符串a中。

分析与解法

此题初看似乎很简单，但要高效地实现并不轻松。而且，如果面试官步步紧逼，一个一个否决你想到的方法，要求你给出更快、更好的方案，恐怕就要费不少脑筋了。

解法一：蛮力轮询

判断短字符串b中的字符是否都在长字符串a中，最直观也是最简单的思路则是：轮询短字符串b中的每一个字符，逐个与长字符串a中的每个字符进行比较，看是否都在字符串a中。

参考代码如下：

bool StringContain(string &a, string &b)
{
 　　for (int i = 0; i < b.length(); ++i)
 　　{
 　　　　int j;
 　　　　for (j = 0; (j < a.length()) && (a[j] != b[i]); ++j)
 　　　　　　;
 　　　　if (j >= a.length())
 　　　　{
 　　　　　　return false;
 　　　　}
 　　}
 　　return true;
}

如果n是长字符串a的长度，m是短字符串b的长度，那么此算法需要O(nm)次比较。显然，如果n和m很大，时间开销太大，需要寻找更好的办法。

解法二：排序后轮询

如果允许排序，可以考虑先排序后轮询。例如，可先对这两个字符串中的字母进行排序，然后再对两个字符串依次轮询。

常规情况下，两个字符串的排序需要O(mlogm)+O(nlogn)次操作，之后的线性扫描需要O(m+n)次操作。关于排序方法，可以采用最常用的快速排序。

参考代码如下：

bool StringContain(string &a, string &b)
{
 　　sort(a.begin(), a.end());
 　　sort(b.begin(), b.end());
 　　for (int pa = 0, pb = 0; pb < b.length();)
 　　{
 　　　　while ((pa < a.length()) && (a[pa] < b[pb]))
 　　　　{
 　　　　　　++pa;
 　　　　}
 　　　　if ((pa >= a.length()) || (a[pa] > b[pb]))
 　　　　{
 　　　　　　return false;
 　　　　}
 　　　　++pb;
 　　}
 　　return true;
}

解法三：素数相乘

有没有比排序后轮询更好的方法呢？

首先，让长字符串a中的每个字母与一个素数对应，如A对应2，B对应3，C对应5，……，依次类推。再遍历长字符串a，把a中的每个字母对应的素数相乘，得到一个整数。然后，让短字符串b中的字母也对应相应的素数，再用b中的每个字母对应的素数除上面得到的整数。如果结果有余数，说明结果为false，当即退出程序；如果整个过程中没有余数，则说明短字符串b是长字符串a的子集。

具体思路总结如下。

（1）按照从小到大的顺序，用26个素数分别代替长字符串a中的所有字母。

（2）遍历长字符串a，求得a中的所有字母对应的素数的乘积。

（3）遍历短字符串b，判断上一步得到的乘积能否被b中的字母对应的素数整除。

（4）输出结果。

上述算法的时间复杂度为O(m+n)。当然，最好情况下的时间复杂度为O(n)，即在遍历短字符串b的第一个字母，与长字符串a中所有字符所对应的素数的乘积相除时，当即出现余数，便直接退出程序，返回false。

bool StringContain(string &a, string &b)
{
 　　const int p[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 };
 　　int f = 1;
 　　for (int i = 0; i < a.length(); ++i)
 　　{
 　　　　int x = p[a[i] - 'A'];
 　　　　if (f % x)
 　　　　{
 　　　　　　f *= x;
 　　　　}
 　　}
 　　for (int i = 0; i < b.length(); ++i)
 　　{
 　　　　int x = p[b[i] - 'A'];
 　　　　if (f % x)
 　　　　{
 　　　　　　return false;
 　　　　}
 　　}
 　　return true;
}

这种素数相乘的方法看似可行，实则不可行，因为素数相乘的结果会很大，从而导致整数溢出（前16个字母对应的素数相乘便会超出long long类型所能表示的最大整数范围）。

解法四：位运算法

如果面试官继续追问，到底有没有更好的办法呢？或许你绞尽脑汁能想到计数排序。但除了计数排序还有别的办法吗？

事实上，可以先把长字符串a中的所有字符都放入一个散列表（hash table）中，然后轮询短字符串b，看b中的每个字符是否都在散列表里，如果都在，说明长字符串a包含短字符串b；否则，说明不包含。

再进一步，可以用位运算（26位整数表示）为长字符串a计算出一个“签名”，再逐一将短字符串b中的字符放到a中进行查找。

参考代码如下：

bool StringContain(string &a, string &b)

{

 　　int hash = 0;

 　　for (int i = 0; i < a.length(); ++i)

 　　{

 　　　　hash |= (1 << (a[