记录20200830
2020-08-30 本文已影响0人
车湾里
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;
}
}
感谢阮一峰大佬的博客，让我看到了第一手的外文信息：
