美文网首页
记录20200830

记录20200830

作者: 车湾里 | 来源:发表于2020-08-30 11:15 被阅读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" 的最短回文串

    1. 将原字符串倒置,r = "cba"
    2. 拼装临时字符串,t = s + "#" + r = "abc#cba"
    3. 用KMP算法,求t的最大公共前后缀,为:a
      t的前缀有,a, ab, abc, abc#, abc#c, abc#cb
      t的后缀有,bc#cba, c#cba, #cba, cba, ba, a
      由上面“人工”智能分析,那么:只有“a” 既出现在前缀中,又出现在后缀中。
    4. 将 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;            
        }
    }
    
    
    

    感谢阮一峰大佬的博客,让我看到了第一手的外文信息:

    相关文章

      网友评论

          本文标题:记录20200830

          本文链接:https://www.haomeiwen.com/subject/izmssktx.html