214. Shortest Palindrome
給定一個字符串 s。你可以通過在字符串前面添加字符將其轉換為回文。
返回可以通過這種轉換找到的最短回文。
範例：
輸入：s = "aacecaaa" 輸出："aaacecaaa"
Python
class Solution:
def shortestPalindrome(self, s: str) -> str:
if not s:
return s
# Create the combined string with a special separator
temp = s + "#" + s[::-1]
# Compute the KMP table (partial match table)
kmp_table = [0] * len(temp)
j = 0
for i in range(1, len(temp)):
while j > 0 and temp[i] != temp[j]:
j = kmp_table[j - 1]
if temp[i] == temp[j]:
j += 1
kmp_table[i] = j
# Length of the longest prefix which is also a suffix
max_len = kmp_table[-1]
# Add the necessary characters in front of s
add_on = s[max_len:][::-1]
return add_on + s
20.90MB, 65ms
C++
class Solution {
public:
string shortestPalindrome(string s) {
if (s.empty()) return s;
// Create the combined string with a special separator
string temp = s + "#" + string(s.rbegin(), s.rend());
// Compute the KMP table (partial match table)
vector<int> kmp_table(temp.size(), 0);
int j = 0;
for (int i = 1; i < temp.size(); ++i) {
while (j > 0 && temp[i] != temp[j]) {
j = kmp_table[j - 1];
}
if (temp[i] == temp[j]) {
++j;
}
kmp_table[i] = j;
}
// Length of the longest prefix which is also a suffix
int max_len = kmp_table.back();
// Add the necessary characters in front of s
string add_on = s.substr(max_len);
reverse(add_on.begin(), add_on.end());
return add_on + s;
}
};
11.62MB, 11ms
Javascript
/**
* @param {string} s
* @return {string}
*/
var shortestPalindrome = function(s) {
if (s.length === 0) return s;
// Create the combined string with a special separator
const temp = s + "#" + s.split('').reverse().join('');
// Compute the KMP table (partial match table)
const kmpTable = new Array(temp.length).fill(0);
let j = 0;
for (let i = 1; i < temp.length; i++) {
while (j > 0 && temp[i] !== temp[j]) {
j = kmpTable[j - 1];
}
if (temp[i] === temp[j]) {
j++;
}
kmpTable[i] = j;
}
// Length of the longest prefix which is also a suffix
const maxLen = kmpTable[temp.length - 1];
// Add the necessary characters in front of s
const addOn = s.slice(maxLen).split('').reverse().join('');
return addOn + s;
};
55.41MB, 68ms
