給定一個字符串 s，你可以通過在字符串前面添加字符將其轉換為回文串。找到并返回可以用這種方式轉換的最短回文串。

示例 1:

輸入: "aacecaaa" 輸出: "aaacecaaa"

示例 2:

輸入: "abcd" 輸出: "dcbabcd"

解題思路一

直覺告訴我們，我們找出左邊的最長回文子串，比如aacecaaa左側最長的回文子串就是aacecaa，然后將右側剩余的部分反轉補到原串的左側即可。由于找的是最長的回文子串，直接從右往左，找到第一個回文子串即可。對應的代碼如下所示

class Solution:def shortestPalindrome(self, s):""":type s: str:rtype: str"""r = 1for i in range(len(s), 0, -1):if s[0:i] == (s[0:i])[::-1]:r = ibreakreturn (s[r:])[::-1] + s

解題思路二

第二種思路相較于第一種思路更為巧妙，利用到了KMP中的fail數(shù)組，也有人叫做next數(shù)組。

因為fail數(shù)組中記錄了最短回退位置，也即保證了回退后所匹配的部分是最長的。我們直接將原串和反轉的原串拼在一起，求出其fail數(shù)組，最后的位置能夠回退到的位置即為左側最長的回文子串。

#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; }

轉載于:https://www.cnblogs.com/crackpotisback/p/10219544.html

總結

以上是生活随笔為你收集整理的leetcode 214. 最短回文串 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。