[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.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

题目大意:

给定一个字符串S,通过向该字符串的首部添加一些字符将其转化为回文。寻找并返回通过这种转化可以得到的最短回文。

测试样例见题目描述。

解题思路:

KMP算法

参考LeetCode Discuss链接:https://leetcode.com/discuss/36807/c-8-ms-kmp-based-o-n-time-%26-o-n-memory-solution

记原始字符串为s,s的反转字符串为rev_s。

构造字符串l = s + '#' + rev_s,其中'#'为s中不会出现的字符,添加'#'是为了处理输入为空字符串的情形。

对字符串l执行KMP算法,可以得到“部分匹配数组”p(也称“失败函数”)

我们只关心p数组的最后一个值p[-1],因为它表明了rev_s与s相互匹配的最大前缀长度。

最后只需要将rev_s的前k个字符与原始串s拼接即可,其中k是s的长度len(s)与p[-1]之差。

Python代码:

class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        rev_s = s[::-1]
        l = s + '#' + rev_s
        p = [0] * len(l)
        for i in range(1, len(l)):
            j = p[i - 1]
            while j > 0 and l[i] != l[j]:
                j = p[j - 1]
            p[i] = j + (l[i] == l[j])
        return rev_s[: len(s) - p[-1]] + s

 

本文链接:http://bookshadow.com/weblog/2015/05/22/leetcode-shortest-palindrome/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 2222 2222 发布于 2015年8月5日 13:38 #

    http://www.rudy-yuan.net/archives/186/

    这个说得挺清楚的

张贴您的评论