数据结构面试题：字符串
1. 确定一个字符串的所有字符是否全都不同
一开始，不妨先问问面试官，上面的字符串是ASCII字符串还是Unicode字符串。这很重要，问这个问题表明你关注细节，并且对计算机科学有深刻了解。
为了简单起见，这里假定字符集为ASCII。若不是的话，则需扩大存储空间，不过其余逻辑没有分别。
假定字符集为ASCII，对于这个问题，我们可以做一个简单的优化，若字符串的长度大于字母表中的字符个数，则直接返回false。毕竟，若字母表只有256个字符，字符串里就不可能有280个各不相同的字符。
第一种解法是构建一个布尔值的数组，索引值i对应的标记指示该字符串是否含有字母表第i个字符。若这个字符第二次出现，则立即返回false。
下面是这个算法的实现代码。
public boolean isUniqueChars2(String str) {
if (str.length() > 256)
return false;
boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) { // 这个字符已在字符串中出现过
return false;
}
char_set[val] = true;
}
return true;
}
这段代码的时间复杂度为O(n)，其中n为字符串长度。空间复杂度为O(1)。
使用位向量（bit vector），可以将空间占用减少为原先的1/8。下面的代码假定字符串只含有小写字母a到z。这样一来，我们只需使用一个int型变量。
public boolean isUniqueChars(String str) {
if (str.length() > 26) return false;
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - ‘a’;
if ((checker & (1 << val)) > 0) {
return false;
}
checker |= (1 << val);
}
return true;
}
另外，还有以下两种解法。
将字符串中的每一个字符与其余字符进行比较。这种方法的时间复杂度为O(n2 )，空间复杂度为O(1)。
若允许修改输入字符串，可以在O(n log(n))时间里对字符串排序，然后线性检查其中有无相邻字符完全相同的情况。不过，值得注意的是，很多排序算法会占用额外的空间。
从某些方面来看，这些算法算不上最优，不过，从问题的限制条件来看，或许还算是不错的解法。
2. 使用C/C++实现反转一个null结尾的字符串
这是很经典的面试题，你可能会忽略的是：不分配额外空间，直接就地反转字符串，另外，还要注意null字符。
void reverse(char *str) {
char* end = str;
char tmp;
if (str) {
// 找出字符串末尾
while (*end) {
++end;
}
// 回退一个字符，最后一个为null字符
--end;
// 从字符串首尾开始交换两个字符，直至两个指针在中间碰头
while (str < end) {
tmp = *str;
*str++ = *end;
*end-- = tmp;
}
}
}
上面的代码只是实现这个解法的诸多方法之一。我们甚至还可以递归实现这段代码，但并不推荐这么做。
3. 确定一个字符串的字符重新排列后能否变成另一个字符串
跟其他许多问题一样，首先我们应该向面试官确认一些细节，弄清楚变位词（anagram）比较是否区分大小写。比如，God是否为dog的变位词？此外，我们还应该问清楚是否要考虑空白字符。
这里假定变位词比较区分大小写，空白也要考虑在内。也就是说，“god ”不是“dog”的变位词。
比较两个字符串时，只要两者长度不同，就不可能是变位词。
解决这个问题有两个简单的解决方法，并且都采用了上述优化，即先比较字符串长度。
解法1：排序字符串
若两个字符串互为变位词，那么它们拥有同一组字符，只不过顺序不同。因此，对字符串排序，组成这两个变位词的字符就会有相同的顺序。我们只需比较排序后的字符串。
public String sort(String s) {
char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}
public boolean permutation(String s, String t) {
if (s.length() != t.length()) {
return false;
}
return sort(s).equals(sort(t));
}
在某种程度上，这个算法算不上最优，不过换个角度看，该算法或许更可取：它清晰、简单且易懂。从实践角度来看，这可能是解决该问题的上佳之选。
不过，要是效率当头，我们可以换种做法。
解法2：检查两个字符串的各字符数是否相同
我们还可以充分利用变位词的定义——组成两个单词的字符数相同——来实现这个算法。我们只需遍历字母表，计算每个字符出现的次数。然后，比较这两个数组即可。
public boolean permutation(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] letters = new int[256]; // 假设条件
char[] s_array = s.toCharArray();
for (char c : s_array) { // 计算字符串s中每个字符出现的次数
letters[c]++;
}
for (int i = 0; i < t.length(); i++) {
int c = (int) t.charAt(i);
if (--letters[c] < 0) {
return false;
}
}
return true;
}
注意第6行的假设条件。在面试中，最好跟面试官核实一下字符集的大小。这里假设字符集为ASCII。
4. 将字符串中的空格全部替换为“%20”
假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
处理字符串操作问题时，常见做法是从字符串尾部开始编辑，从后往前反向操作。这种做法很有用，因为字符串尾部有额外的缓冲，可以直接修改，不必担心会覆写原有数据。
我们将采用上面这种做法。该算法会进行两次扫描。第一次扫描先数出字符串中有多少空格，从而算出最终的字符串有多长。第二次扫描才真正开始反向编辑字符串。检测到空格则将%20复制到下一个位置，若不是空白，就复制原先的字符。
下面是这个算法的实现代码。
public void replaceSpaces(char[] str, int length) {
int spaceCount = 0, newLength, i;
for (i = 0; i < length; i++) {
if (str[i] == ‘ ’) {
spaceCount++;
}
}
newLength = length + spaceCount * 2;
str[newLength] = ‘\0’;
for (i = length - 1; i >= 0; i--) {
if (str[i] == ‘ ’) {
str[newLength - 1] = ‘0’;
str[newLength - 2] = ‘2’;
str[newLength - 3] = ‘%’;
newLength = newLength - 3;
} else {
str[newLength - 1] = str[i];
newLength = newLength - 1;
}
}
}
因为Java字符串是不可变的（immutable），所以我们选用了字符数组来解决这个问题。若直接使用字符串，返回时就要把字符串复制一份，不过，这么做的好处是只需扫描一次。
5. 利用字符重复出现的次数实现基本的字符串压缩功能
比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。
乍一看，编写这个方法似乎相当简单，实则有点复杂。我们会迭代访问字符串，将字符拷贝至新字符串，并数出重复字符。这能有多难呢？
public String compressBad(String str) {
String mystr = "";
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) { // 找到重复字符
count++;
} else { // 插入字符的数目，更新last字符
mystr += last + “” + count;
last = str.charAt(i);
count = 1;
}
}
return mystr + last + count;
}
这段代码并未处理压缩后字符串比原始字符串长的情况，但除此之外，全都满足要求。这种做法效率够高吗？不妨分析一下这段代码的执行时间。
这段代码的执行时间为O(p + k2 )，其中p为原始字符串长度，k为字符序列的数量。比如，若字符串为aabccdeeaa，则总计有6个字符序列。执行速度慢的原因是字符串拼接操作的时间复杂度为O(n2 )（参见8.1节的StringBuffer部分）。
我们可以使用StringBuffer优化部分性能。
String compressBetter(String str) {
/* 检查压缩后的字符串是否会变得更长*/
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
StringBuffer mystr = new StringBuffer();
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) { // 找到重复字符
count++;
} else { // 插入字符的数目，更新last字符
mystr.append(last); // 插入字符
mystr.append(count); // 插入数目
last = str.charAt(i);
count = 1;
}
}
/* 在上面第15到16行，当重复字符改变时，
* 才会插入字符。我们还需在函数末尾更新
* 字符串，因为最后一组重复字符还未放入
* 压缩字符串中。
*/
mystr.append(last);
mystr.append(count);
return mystr.toString();
}
int countCompression(String str) {
if (str == null || str.isEmpty())
return 0;
char last = str.charAt(0);
int size = 0;
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) {
count++;
} else {
last = str.charAt(i);
size += 1 + String.valueOf(count).length();
count = 1;
}
}
size += 1 + String.valueOf(count).length();
return size;
}
这个算法要好得多。注意，我们在第2～5行代码中加入了长度检查。
若不想或不能使用StringBuffer，我们还是可以高效地解决这个问题。第2行代码会算出字符串压缩后的长度，这样就可以构建出相应大小的字符数组，代码实现如下：
String compressAlternate(String str) {
/* 检查压缩后的字符串是否会变得更长*/
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
char[] array = new char[size];
int index = 0;
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) { // 找到重复字符
count++;
} else {
/* 更新重复字符的数目*/
index = setChar(array, last, index, count);
last = str.charAt(i);
count = 1;
}
}
/* 以最后一组重复字符更新字符串*/
index = setChar(array, last, index, count);
return String.valueOf(array);
}
int setChar(char[] array, char c, int index, int count) {
array[index] = c;
index++;
/* 将数目转换成字符串，然后转成字符数组*/
char[] cnt = String.valueOf(count).toCharArray();
/* 从最大的数字到最小的，复制字符*/
for (char x : cnt) {
array[index] = x;
index++;
}
return index;
}
int countCompression(String str) {
/* 与之前实现相同*/
}
跟第二种解法一样，执行上述代码的时间复杂度为O(N)，空间复杂度为O(N)。
6. 判断一个字符串是否由另一个字符串旋转而来
假定有一个方法isSubstring，可检查一个单词是否为其他字符串的子串。给定两个字符串s1 和s2，请编写代码检查s2 是否为s1 旋转而成，要求只能调用一次isSubstring。（比如，waterbottle是erbottlewat旋转后的字符串。）
假定s2由s1旋转而成，那么，我们可以找出旋转点在哪。例如，若以wat对waterbottle旋转，就会得到erbottlewat。在旋转字符串时，我们会把s1切分为两部分：x和y，并将它们重新组合成s2。
s1 = xy = waterbottle
x = wat
y = erbottle
s2 = yx = erbottlewat
因此，我们需要确认有没有办法将s1切分为x和y，以满足xy = s1和yx = s2。不论x和y之间的分割点在何处，我们会发现yx肯定是xyxy的子串。也即，s2总是s1s1的子串。
上述分析正是这个问题的解法：直接调用isSubstring(s1s1, s2)即可。
下面是上述算法的实现代码。
public boolean isRotation(String s1, String s2) {
int len = s1.length();
/* 检查s1和s2是否等长且不为空*/
if (len == s2.length() && len > 0) {
/* 拼接s1和s1，放入新字符串中*/
String s1s1 = s1 + s1;
return isSubstring(s1s1, s2);
}
return false;
}