14.面试算法-字符串常见算法题（三）

1. 字符串回文问题

1.1 LeetCode.125. 验证回文串

回文问题在链表中是重点，在字符串中同样是个重点。当初我去美团面试第一轮技术面的第一个算法题就是让写判断字符串回文的问题。

这个本身还是比较简单的，只要先转换成字符数组，然后使用双指针方法从两头到中间比较就行了。也许是过于简单了吧，面试时经常被加餐，例如LeetCode里的两道题。一个是普通的验证回文串，第二个是找最长的子回文串。第二个问题需要动态规划等技术，有点难度，如果感兴趣可以自行去了解下，这里先看一下基本的。

题目：

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

示例1：
输入 : “A man, a plan, a canal: Panama” 输出 : true
解释： “amanaplanacanalpanama” 是回文串
示例2：
输入 : “race a car” 输出 : false
解释： “raceacar” 不是回文串
示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

分析

最简单的方法是对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。

判断的方法有两种。第一种是使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么 sgood 就是回文串。

class Solution {public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}StringBuffer sgood_rev = new StringBuffer(sgood).reverse();return sgood.toString().equals(sgood_rev.toString());}
}

第二种是使用双指针。初始时，左右指针分别指向 sgood 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 sgood 时回文串。

class Solution {public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}int n = sgood.length();int left = 0, right = n - 1;while (left < right) {if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {return false;}++left;--right;}return true;}
}

2. 字符串简单搜索问题

我们为什么叫简单搜索问题呢？因为字符串的有些搜索问题非常复杂，需要dp或者更高级的算法，例如字符匹配等等，因此这里我们先看几个简单的情况。

2.1 LeetCode387. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例 1：
输入: s = “leetcode”
输出: 0
示例 2:
输入: s = “loveleetcode”
输出: 2
示例 3:
输入: s = “aabb”
输出: -1

提示：s 只包含小写字母

我们可以对字符串进行两次遍历，在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 -1。

class Solution {public int firstUniqChar(String s) {Map<Character, Integer> frequency = new HashMap<Character, Integer>();for (int i = 0; i < s.length(); ++i) {char ch = s.charAt(i);frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);}for (int i = 0; i < s.length(); ++i) {if (frequency.get(s.charAt(i)) == 1) {return i;}}return -1;}
}

2.2 LeetCode58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：
输入：s = “Hello World”
输出：5
解释：最后一个单词是“World”，长度为 5。
示例 2：
输入：s = " fly me to the moon "
输出：4
解释：最后一个单词是“moon”，长度为 4。
示例 3：
输入：s = “luffy is still joyboy”
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

分析
这个题还是比较简单的，反向遍历。题目要求得到字符串中最后一个单词的长度，可以反向遍历字符串，寻找最后一个单词并计算其长度。

由于字符串中至少存在一个单词，因此字符串中一定有字母。首先找到字符串中的最后一个字母，该字母即为最后一个单词的最后一个字母。

从最后一个字母开始继续反向遍历字符串，直到遇到空格或者到达字符串的起始位置。遍历到的每个字母都是最后一个单词中的字母，因此遍历到的字母数量即为最后一个单词的长度。

class Solution {public int lengthOfLastWord(String s) {int index = s.length() - 1;while (s.charAt(index) == ' ') {index--;}int wordLength = 0;while (index >= 0 && s.charAt(index) != ' ') {wordLength++;index--;}return wordLength;}
}

3. 旋转和重排

3.1 [剑指Offer】 58. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例1：
输入 : s = “abcdefg”, k = 2
输出 : “cdefgab”
示例2：
输入 : s = “lrloseumgh”, k = 6
输出 : “umghlrlose”

本题有多种方式处理的，最直观的方式是前面剪贴下来的若干字符和后面的字符保存到两个数组里，然后再按照要求合并就行了。这个在go、JavaScript 、python等语言中有切片的操作，可以非常方便地处理，java中虽然没有切片，但是可以通过子串来实现相同的功能。

class Solution {public String reverseLeftWords(String s, int n) { if (s == null || s.length() == 0) {return s;}return s.substring(n, s.length()) + s.substring(0, n);}
}

第二种方式是通过StringBuilder来实现拼接，先将第k个之后的元素添加进来，然后再将前k个添加进来，代码如下：

class Solution {public String reverseLeftWords(String s, int n) { if (s == null || s.length() == 0) {return s;}StringBuilder res = new StringBuilder();for(int i = n; i < s.length(); i++)res.append(s.charAt(i));for(int i = 0; i < n; i++)res.append(s.charAt(i));return res.toString();}
}

很明显上面两个都需要记住StringBuilder等的用法，如果使用最简单的String和char数组来处理怎么做呢？前面我们已经介绍过，所以这里只要看一下就明确了：

class Solution {public String reverseLeftWords(String s, int n) { if (s == null || s.length() == 0) {return s;}String res = "";for(int i = n; i < s.length(); i++)res += s.charAt(i);for(int i = 0; i < n; i++)res += s.charAt(i);return res;}
}

3.2 判定是否互为字符重排

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例1：
输入 : s1 = “abcadfhg”, s2 = “bcafdagh” ’
输出 : true
示例2：
输入 : s1 = “abc”, s2 = “bad”
输出 : false

这个题第一眼看，感觉是个排列组合的题目，然后如果使用排列的算法来处理，难度会非常大，而且效果还不一定好。用简单的方式就能解决。

第一种方法：将两个字符串全部从小到大或者从大到小排列，然后再逐个位置比较，这时候不管两个原始字符串是什么，都可以判断出来。

代码也不复杂：

public boolean checkPermutation(String s1, String s2) { // 将字符串转换成字符数组char[] s1Chars = s1.toCharArray(); char[] s2Chars = s2.toCharArray();// 对字符数组进行排序Arrays.sort(s1Chars); Arrays.sort(s2Chars);// 再将字符数组转换成字符串，比较是否相等return new String(s1Chars).equals(new String(s2Chars));
}

注意这里我们使用了Arrays.sort()，你是否记得我们在数组一章提到过这个方法必须牢记。

第二种方法：使用Hash，注意这里我们不能简单的存是否已经存在，因为字符可能在某个串里重复存在例如"abac"。我们可以记录出现的次数，如果一个字符串经过重新排列后，能够变成另外一个字符串，那么它们的每个不同字符的出现次数是相同的。如果出现次数不同，那么表示两个字符串不能够经过重新排列得到。

这个代码逻辑不复杂，但是写起来稍微长一点：

class Solution {public boolean checkPermutation(String s1, String s2) {if (s1.length() != s2.length()) {return false;}char[] s1Chars = s1.toCharArray();Map<Character, Integer> s1Map = getMap(s1);Map<Character, Integer> s2Map = getMap(s2);for (char s1Char : s1Chars) {if (!s2Map.containsKey(s1Char) || s2Map.get(s1Char) != s1Map.get(s1Char)) {return false;}}return true;}// 统计指定字符串str中各字符的出现次数，并以Map的形式返回private Map<Character, Integer> getMap(String str) {Map<Character, Integer> map = new HashMap<>();char[] chars = str.toCharArray();for (char aChar : chars) {map.put(aChar, map.getOrDefault(aChar, 0) + 1);}return map;}
}

拓展

这个题还有一种方法，就是不管原始字符串有多长，是什么，基本元素都是26个英文字母，只少不多，那么我们可以换个思维：为两个字符串分别建立两个大小为26的字母表数组，每个位置是对应的字母出现的次数。最后统计一下两个数组的字母数和每个字母出现的次数就可以了。

这种方法其实也是文本搜索引擎的基本思想，例如 elasticSearch等，在文本搜索里有个专门的名字，叫“倒排索引”。看一下实现代码：

public class Solution {public boolean CheckPermutation(String s1, String s2) {if (s1.length() != s2.length()) {return false;}int[] c1 = count(s1);int[] c2 = count(s2);for (int i = 0; i < c1.length; i++) {if (c1[i] != c2[i]) {return false;}}return true;}private int[] count(String str) {int[] c = new int[26];char[] chars = str.toCharArray();for (char aChar : chars) {c[aChar - 'a']++;}return c;}
}

4. 最长公共前缀

这是一道经典的字符串问题，先看题目要求：

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

示例1：
输入：strs = [“flower”,“flow”,“flight”]
输出： “fl”
示例2：
输入：strs = [“dog”,“racecar”,“car”]
输出： “”
解释：输入不存在公共前缀。

要解答这个问题，我们需要先看一下公共前缀的分布有什么特点，如下图：
在这里插入图片描述
可以看到，第一种方式，我们可以竖着比较，如左图所示，每前进一个位置就比较各个串，看是不是都是相等的，只要在某一轮遇到一个不相等的，那么就结束。

第二种方式，还可以横着比较，先比较前两个找到公共前缀fix1，然后再和第三个比较公共前缀得到fix2，我们可以确定fix2一定不会比fix1更长，然后和第四个比较，得到fix4，一直到最后一个fixn。每次得到的fix都不会比前面的长，最后比较完了还剩下的就是需要找的前缀了。

看到这里你是否有种似曾相识的感觉，我们前面合并K个数组或者K个链表不也是类似的思路吗？是的，就是类似的思路。

第三种方式，我们是否可以对第二种进行优化一下，借鉴归并的思想，先两两一组找fix，然后将找到的fix再两两归并呢？当然可以了，这就是归并的方式。

先看第一种的实现方法，竖着比较。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

class Solution {public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) {return "";}int length = strs[0].length();int count = strs.length;for (int i = 0; i < length; i++) {char c = strs[0].charAt(i);for (int j = 1; j < count; j++) {if (i == strs[j].length() || strs[j].charAt(i) != c) {return strs[0].substring(0, i);}}}return strs[0];}
}

第二种是横着依次比较，依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀（其实就是看是否要缩短，一定不会变长），当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。

如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。

class Solution {public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];int count = strs.length;for (int i = 1; i < count; i++) {prefix = longestCommonPrefix(prefix, strs[i]);if (prefix.length() == 0) {break;}}return prefix;}public String longestCommonPrefix(String str1, String str2) {int length = Math.min(str1.length(), str2.length());int index = 0;while (index < length && str1.charAt(index) == str2.charAt(index)) {index++;}return str1.substring(0, index);}
}

再看第三种，归并方法，这种方式也可以叫分治，就是先两两判断，之后再两两比较，直到得到最终的结果。

class Solution {public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) {return "";} else {return longestCommonPrefix(strs, 0, strs.length - 1);}}public String longestCommonPrefix(String[] strs, int start, int end) {if (start == end) {return strs[start];} else {int mid = (end - start) / 2 + start;String lcpLeft = longestCommonPrefix(strs, start, mid);String lcpRight = longestCommonPrefix(strs, mid + 1, end);return commonPrefix(lcpLeft, lcpRight);}}public String commonPrefix(String lcpLeft, String lcpRight) {int minLength = Math.min(lcpLeft.length(), lcpRight.length());for (int i = 0; i < minLength; i++) {if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {return lcpLeft.substring(0, i);}}return lcpLeft.substring(0, minLength);}
}

5. 字符串压缩问题

这个题也是出现频率很高的题目，经常在面经中看到。实现起来略有难度，我们一起看一下。

题目要求

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组连续重复字符：

如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在修改完输入数组后，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例 1：
输入：chars = [“a”,“a”,“b”,“b”,“c”,“c”,“c”]
输出：返回 6 ，输入数组的前 6 个字符应该是：[“a”,“2”,“b”,“2”,“c”,“3”]
解释：“aa” 被 “a2” 替代。“bb” 被 “b2” 替代。“ccc” 被 “c3” 替代。
示例 2：
输入：chars = [“a”]
输出：返回 1 ，输入数组的前 1 个字符应该是：[“a”]
解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。
示例 3：
输入：chars = [“a”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”]
输出：返回 4 ，输入数组的前 4 个字符应该是：[“a”,“b”,“1”,“2”]。
解释：由于字符 “a” 不重复，所以不会被压缩。“bbbbbbbbbbbb” 被 “b12” 替代。

这个题貌似采用双指针策略来处理就行，但是再分析发现三个指针才够。

我们可以使用两个指针分别标志我们在字符串中读和写的位置，还要一个指针left用来标记重复字段的开始位置。read指针不断向前读取，每次当读指针read 移动到某一段连续相同子串的最右侧，我们就在写指针 write 处依次写入该子串对应的字符和子串长度即可。

当读指针read位于字符串的末尾，或读指针read指向的字符不同于下一个字符时，我们就认为读指针read 位于某一段连续相同子串的最右侧。该子串对应的字符即为读指针 read 指向的字符串。我们使用变量 left 记录该子串的最左侧的位置，这样子串长度即为 read-left+1。

这里还有一个问题，就是长度可能超过10，因此还要实现将数字转化为字符串写入到原字符串的功能。这里我们采用短除法将子串长度倒序写入原字符串中，然后再将其反转即可。

class Solution {public int compress(char[] chars) {int n = chars.length;int write = 0, left = 0;for (int read = 0; read < n; read++) {if (read == n - 1 || chars[read] != chars[read + 1]) {chars[write++] = chars[read];int num = read - left + 1;if (num > 1) {int anchor = write;while (num > 0) {chars[write++] = (char) (num % 10 + '0');num /= 10;}reverse(chars, anchor, write - 1);}left = read + 1;}}return write;}public void reverse(char[] chars, int left, int right) {while (left < right) {char temp = chars[left];chars[left] = chars[right];chars[right] = temp;left++;right--;}}
}