LeetCode.214.最短回文串（困难）

题目

LeetCode.214.最短回文串（困难）

给定一个字符串 _s_，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

题解

思路

回文串的特点是左右两端字符相同，要在s前面添加字符串使得新字符串是回文串，那就把s的倒置字符串放在前面就可以形成回文了。

s的倒置字符串添加在s前面会有什么问题？

这样添加还不是最短的回文。

比如s是abbacd，添加dcabba到开头，形成dcabbaabbacd，可以发现abba是多余的，不用添加，dcabbacd是更短的回文串，只要添加dc就行了。

应该添加什么样的字符串才能获得最短回文？

得找到abbacd的前缀和dcabba的后缀最长的重合的部分的长度，然后找到不重复的部分，添加到字符串前面。

标准化描述：

• 设s'是s的倒置字符串。
• 求s的前缀和s'的后缀中相同部分最长的长度x。
• 取s的子串s[x, n - 1]，倒置后添加到s前面，形成最短回文。

怎么寻找s和s的倒置字符串最长前后缀？

联想到kmp做字符串匹配时，要先求一个前缀函数，前缀函数prefix[i]表示s[0, i]中最长的公共前后缀的长度，只要求出前缀函数就可以求解题目。

前缀函数怎么求？

一句话：让s[0, n - 1]匹配s[1, n - 1]。

算法步骤：

• 双指针i和j遍历s。
• i从1开始，j从0开始。
• s匹配自己，字符能匹配上，双指针都前进。
• 当前s[i]和s[j]不匹配，要把j往回退。
  • j退到前一个位置（j - 1）的最长公共前后缀的前缀的下一个字符的位置。继续拿s[j]跟s[i]尝试匹配，如果能匹配的上，prefix[i]就求出来了。
  • 如果j一直回退，最坏也就是回退到0，因为prefix[0] = 0（一个字符不存在前后缀），没的退了，只能比较s[i]和s[0]，没匹配的话公共前后缀长度就是0。

前缀函数应该针对哪个字符串求？

我们要求s的前缀和s的倒置字符串的后缀最长的公共部分。
所以弄一个新字符串 s' + s。

这样存在一个问题，如果所有字符都相同，此时最长公共前后缀就是整个字符串s' + s本身，这不是期望的结果，所以连接s'和s时，中间隔一个用不到的字符，比如#。

class Solution {
    fun shortestPalindrome(s: String): String {
        if (s.isEmpty()) return ""
        // 加#是为了防止出现全部重复的字符，这样最长公共前后缀的长度就不是期望的了
        val maxLength = (s + "#" + s.reversed()).prefixArray().last()
        return s.substring(maxLength).reversed() + s
    }

    private fun String.prefixArray(): IntArray {
        val s = this
        val n = length
        val prefix = IntArray(n) { 0 }
        for (i in 1 until n) {
            var j = prefix[i - 1]
            while (j > 0 && s[i] != s[j]) j = prefix[j - 1]
            if (s[i] == s[j]) j++
            prefix[i] = j
        }
        return prefix
    }
}

复杂度

设字符串s长度为n。

• 时间复杂度O(n)：求前缀函数最坏情况需要O(n + n) = O(n)时间；还要遍历整个s' + s，有2n的长度，需要O(n)时间。
• 空间复杂度O(n)：前缀函数占用O(n)空间。

kmp时间复杂度推导可参考：

• KMP时间复杂度分析
• KMP算法的时间复杂度是如何计算的？