LeetCode 214题,最短回文数
利用 Python 切片
class Solution:
def shortestPalindrome(self, s: str) -> str:
# 倒过来
r = s[::-1]
# 循环,对倒过来的字符串切片,从0开始切片,如果原字符串是以切片出来的字符串开头,那么就找到了最短的回文串
for i in range(len(s) + 1):
# 从0开始切片,找到则将切片剩余部分,左补
if r.endswith(s[:-i]):
return r + s[-i:]
KMP解法
比如求 s = "abc" 的最短回文串
- 将原字符串倒置,r = "cba"
- 拼装临时字符串,t = s + "#" + r = "abc#cba"
- 用KMP算法,求t的最大公共前后缀,为:a
t的前缀有,a, ab, abc, abc#, abc#c, abc#cb
t的后缀有,bc#cba, c#cba, #cba, cba, ba, a
由上面“人工”智能分析,那么:只有“a” 既出现在前缀中,又出现在后缀中。 - 将 r 去掉最大公共前后缀 "a",拼接在 s 前面
即:最短回文串 result = "cb" + "abc" = "cbabc"
经过上面的分析,解题的关键就是 求t的最大公共前后缀。
中文论坛里面流行讲的是 next 数组
https://leetcode-cn.com/problems/shortest-palindrome/solution/tu-jie-kmpsuan-fa-by-yangbingjie/
而一个外国大神讲的是:The Partial Match Table
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
无论是 next 数组,还是 Partial Match Table 他们的核心原理都是最大公共前后缀。
区别在于,next数组的长度比原字符串多1位,然后在第一个位置放了一个傀儡(-1或者0都行)
而, Partial Match Table不用整这个傀儡,代码如下(LeetCode测试通过):
class Solution {
int partial_match_table(String pattern) {
char[] ch = pattern.toCharArray();
int size = pattern.length();
int[] next = new int[size]; //用于存放最大公共前后缀长度
next[0] = 0; // 字符串第一个没有前后缀,最大公共前后缀长度=0
int i = 1; // i 表示next数组的索引,只前进,不回溯
int k = 0; // k 用于比较的字符串索引
while (i < next.length) {
// i指针第1个和 k指针第0个比较
if (ch[i] == ch[k]) { // 相等的话,则 i 继续走, k 记录最大前后缀的长度,相当于k也继续走
next[i] = k + 1;
k = next[i];
++i;
} else if (k == 0) {
// 不相等,并且此时k没有长度,i继续走, 记录当前的匹配长度为0
next[i] = 0;
++i;
} else {
// i不变,对K进行回溯
k = next[k - 1];
}
}
return next[size - 1];
}
public String shortestPalindrome(String s) {
if (s.length() == 0)
return "";
String str=s+'#'+new StringBuilder(s).reverse();
int add=partial_match_table(str);
return new StringBuilder(s.substring(add)).reverse()+s;
}
}
感谢阮一峰大佬的博客,让我看到了第一手的外文信息:
网友评论