leetcode 214. 最短回文串解题报告

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

示例 1:

输入: "aacecaaa"

输出: "aaacecaaa"

示例 2:

输入: "abcd"

输出: "dcbabcd"

解题思路一

直觉告诉我们，我们找出左边的最长回文子串，比如aacecaaa左侧最长的回文子串就是aacecaa，然后将右侧剩余的部分反转补到原串的左侧即可。由于找的是最长的回文子串，直接从右往左，找到第一个回文子串即可。对应的代码如下所示

class Solution:

    def shortestPalindrome(self, s):

        """

        :type s: str

        :rtype: str

        """

        r = 1

        for i in range(len(s), 0, -1):

            if s[0:i] == (s[0:i])[::-1]:

                r = i

                break

        return (s[r:])[::-1] + s

解题思路二

第二种思路相较于第一种思路更为巧妙，利用到了KMP中的fail数组，也有人叫做next数组。

因为fail数组中记录了最短回退位置，也即保证了回退后所匹配的部分是最长的。我们直接将原串和反转的原串拼在一起，求出其fail数组，最后的位置能够回退到的位置即为左侧最长的回文子串。

#include<bits/stdc++.h>

using namespace std;

static auto x = []() {

    std::ios::sync_with_stdio(false);

    std::cin.tie(NULL);

    return 0;

}

();

const int maxn = 100010;

int fail[maxn];

class Solution {

public:

    string shortestPalindrome(string s) {

        string t(s);

        reverse(t.begin(), t.end());

        string st = s + "#" + t;

        int sz = st.size();

        for(int i = 0,j = fail[0] = -1; i < sz; ++i) {

            while(j != -1 && st[i] != st[j])

                j = fail[j];

            fail[i + 1] = ++j;

            if(st[i + 1] == st[j])

                fail[i+1] = fail[j];

        }

        return t.substr(0, t.size()-fail[sz]) + s;

    }

};

int main() {

    return 0;

}

巴特西

leetcode 214. 最短回文串解题报告

解题思路一

解题思路二

最新文章

热门文章

巴特西

leetcode 214. 最短回文串 解题报告

解题思路一

解题思路二

最新文章

热门文章

leetcode 214. 最短回文串解题报告