214. Shortest Palindrome
Đề Bài
You are given a string s. You can convert s to a palindrome by adding characters in front of it.
Return the shortest palindrome you can find by performing this transformation.
Example 1:
Input: s = "aacecaaa" Output: "aaacecaaa"
Example 2:
Input: s = "abcd" Output: "dcbabcd"
Constraints:
0 <= s.length <= 5 * 104sconsists of lowercase English letters only.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(1)
Lời Giải
C++
0214-shortest-palindrome.cpp
class Solution {
public:
string shortestPalindrome(string s) {
const long long base = 4;
const long long mod = 1e9 + 13;
long long p1 = 0;
long long p2 = 0;
long long dummy_base = 1;
int p = 0;
const int n = s.size();
for (int i = 0; i < n; ++i) {
char c = s[i];
p1 = ((c - 'a' + 1) + p1*base) % mod;
p2 = ((c - 'a' + 1)*dummy_base + p2) % mod;
dummy_base = (dummy_base * base) % mod;
if (p1 == p2) {
p = i;
}
}
string t = s.substr(min(p + 1, n));
reverse(t.begin(), t.end());
return t + s;
}
};
Python
0214-shortest-palindrome.py
class Solution:
def shortestPalindrome(self, s: str) -> str:
oh, rh = 0, 0
op = 1
base, mod = 26, 10**9 + 13
sp = 0
n = len(s)
for i in range(n):
oh = (oh + (ord(s[i]) - ord('a') + 1)*op) % mod
op = (op*base) % mod
rh = (rh*base + (ord(s[i]) - ord('a') + 1)) % mod
if oh == rh:
sp = i
return s[sp + 1:][::-1] + s