[LeetCode] Shortest Palindrome 最短回文串

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

这道题让我们求最短的回文串,LeetCode 中关于回文串的其他的题目有 Palindrome NumberValidate PalindromePalindrome PartitioningPalindrome Partitioning II 和 Longest Palindromic Substring。题目让在给定字符串s的前面加上最少个字符,使之变成回文串,来看题目中给的两个例子,最坏的情况下是s中没有相同的字符,那么最小需要添加字符的个数为 s.size() - 1 个,第一个例子的字符串包含一个回文串,只需再在前面添加一个字符即可,还有一点需要注意的是,前面添加的字符串都是从s的末尾开始,一位一位往前添加的,那么只需要知道从s末尾开始需要添加到前面的个数。

首先还是先将待处理的字符串s翻转得到t,然后比较原字符串s和翻转字符串t,从第一个字符开始逐一比较,如果相等,说明s本身就是回文串,不用添加任何字符,直接返回即可;如果不相等,s去掉最后一位,t去掉第一位,继续比较,以此类推直至有相等,或者循环结束,这样就能将两个字符串在正确的位置拼接起来了,代码请参见评论区5楼。但这种写法却会超时 TLE,无法通过 OJ,所以需要用一些比较巧妙的方法来解。

这里使用双指针来找出字符串s的最长回文前缀的大概范围,这里所谓的最长回文前缀是指从开头开始到某个位置为止是回文串,比如 "abbac" 这个子串,可以知道前四个字符组成的回文串 "abba" 就是最长回文前缀。方法是指针i和j分别指向s串的开头和末尾,若 s[i] 和 s[j] 相等,则i自增1,j自减1,否则只有j自减1。需要注意的是,这样遍历一遍后,得到的范围 [0, i) 中的子串并不一定就是最大回文前缀,也可能还需要添加字符,举个例子来说,对于 "adcba",在 for 循环执行之后,i=2,可以发现前面的 "ad" 并不是最长回文前缀,其本身甚至不是回文串,需要再次调用递归函数来填充使其变为回文串,但可以确定的是可以添加最少的字符数让其变为回文串。而且可以确定的是后面剩余的部分肯定不属于回文前缀,此时提取出剩下的字符,翻转一下加到最前面,而对范围 [0, i) 内的子串再次递归调用本函数,这样,在子函数最终会组成最短的回文串,从而使得整个的回文串就是最短的,参见代码如下:

C++ 解法一:

class Solution {
public:
string shortestPalindrome(string s) {
int i = , n = s.size();
for (int j = n - ; j >= ; --j) {
if (s[i] == s[j]) ++i;
}
if (i == n) return s;
string rem = s.substr(i);
reverse(rem.begin(), rem.end());
return rem + shortestPalindrome(s.substr(, i)) + s.substr(i);
}
};

Java 解法一:

public class Solution {
public String shortestPalindrome(String s) {
int i = 0, n = s.length();
for (int j = n - 1; j >= 0; --j) {
if (s.charAt(i) == s.charAt(j)) ++i;
}
if (i == n) return s;
String rem = s.substring(i);
String rem_rev = new StringBuilder(rem).reverse().toString();
return rem_rev + shortestPalindrome(s.substring(0, i)) + rem;
}
}

其实这道题的最快的解法是使用 KMP 算法,KMP 算法是一种专门用来匹配字符串的高效的算法,具体方法可以参见博主之前的这篇博文 KMP Algorithm 字符串匹配算法KMP小结。把s和其转置r连接起来,中间加上一个其他字符,形成一个新的字符串t,还需要一个和t长度相同的一位数组 next,其中 next[i] 表示从 t[i] 到开头的子串的相同前缀后缀的个数,具体可参考 KMP 算法中解释。最后把不相同的个数对应的字符串添加到s之前即可,代码如下:

C++ 解法二:

class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
string t = s + "#" + r;
vector<int> next(t.size(), );
for (int i = ; i < t.size(); ++i) {
int j = next[i - ];
while (j > && t[i] != t[j]) j = next[j - ];
next[i] = (j += t[i] == t[j]);
}
return r.substr(, s.size() - next.back()) + s;
}
};

Java 解法二:

public class Solution {
public String shortestPalindrome(String s) {
String r = new StringBuilder(s).reverse().toString();
String t = s + "#" + r;
int[] next = new int[t.length()];
for (int i = 1; i < t.length(); ++i) {
int j = next[i - 1];
while (j > 0 && t.charAt(i) != t.charAt(j)) j = next[j - 1];
j += (t.charAt(i) == t.charAt(j)) ? 1 : 0;
next[i] = j;
}
return r.substring(0, s.length() - next[t.length() - 1]) + s;
}
}

从上面的 Java 和 C++ 的代码中,可以看出来 C++ 和 Java 在使用双等号上的明显的不同,感觉 Java 对于双等号对使用更加苛刻一些,比如 Java 中的双等号只对 primitive 类数据结构(比如 int, char 等)有效,但是即便有效,也不能将结果直接当1或者0来用。而对于一些从 Object 派生出来的类,比如 Integer 或者 String 等,不能直接用双等号来比较,而是要用其自带的 equals() 函数来比较,因为双等号判断的是不是同一个对象,而不是他们所表示的值是否相同。同样需要注意的是,Stack 的 peek() 函数取出的也是对象,不能直接和另一个 Stack 的 peek() 取出的对象直接双等,而是使用 equals 或者先将其中一个强行转换成 primitive 类,再和另一个强行比较。

下面这种方法的写法比较简洁,虽然不是明显的 KMP 算法,但是也有其的影子在里面。这种 Java 写法也是在找相同的前缀后缀,但是并没有每次把前缀后缀取出来比较,而是用两个指针分别指向对应的位置比较,然后用 end 指向相同后缀的起始位置,最后再根据 end 的值来拼接两个字符串。有意思的是这种方法对应的 C++ 写法会 TLE,跟上面正好相反,那么我们是否能得出 Java 的 substring 操作略慢,而 C++ 的 reverse 略慢呢,博主也仅仅是猜测而已。

Java 解法三:

public class Solution {
public String shortestPalindrome(String s) {
int i = 0, end = s.length() - 1, j = end;
char arr = s.toCharArray();
while (i < j) {
if (arr[i] == arr[j]) {
++i; --j;
} else {
i = 0; --end; j = end;
}
}
return new StringBuilder(s.substring(end + 1)).reverse().toString() + s;
}
}

Github 同步地址:

https://github.com/grandyang/leetcode/issues/214

类似题目:

Longest Palindromic Subsequence

Implement strStr()

Palindrome Pairs

参考资料:

https://leetcode.com/problems/shortest-palindrome/

https://leetcode.com/problems/shortest-palindrome/discuss/60098/My-7-lines-recursive-Java-solution

https://leetcode.com/problems/shortest-palindrome/discuss/60113/Clean-KMP-solution-with-super-detailed-explanation

https://leetcode.com/problems/shortest-palindrome/discuss/60106/My-9-lines-three-pointers-Java-solution-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中...)

上一篇:[LeetCode] 214. Shortest Palindrome 最短回文串


下一篇:Oracle Tuning (Oracle 性能调整)的一些总结