Description#
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 * 104s consists of lowercase English letters only.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def shortestPalindrome(self, s: str) -> str:
base = 131
mod = 10**9 + 7
n = len(s)
prefix = suffix = 0
mul = 1
idx = 0
for i, c in enumerate(s):
prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
mul = (mul * base) % mod
if prefix == suffix:
idx = i + 1
return s if idx == n else s[idx:][::-1] + s
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public String shortestPalindrome(String s) {
int base = 131;
int mul = 1;
int mod = (int) 1e9 + 7;
int prefix = 0, suffix = 0;
int idx = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int t = s.charAt(i) - 'a' + 1;
prefix = (int) (((long) prefix * base + t) % mod);
suffix = (int) ((suffix + (long) t * mul) % mod);
mul = (int) (((long) mul * base) % mod);
if (prefix == suffix) {
idx = i + 1;
}
}
if (idx == n) {
return s;
}
return new StringBuilder(s.substring(idx)).reverse().toString() + s;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| typedef unsigned long long ull;
class Solution {
public:
string shortestPalindrome(string s) {
int base = 131;
ull mul = 1;
ull prefix = 0;
ull suffix = 0;
int idx = 0, n = s.size();
for (int i = 0; i < n; ++i) {
int t = s[i] - 'a' + 1;
prefix = prefix * base + t;
suffix = suffix + mul * t;
mul *= base;
if (prefix == suffix) idx = i + 1;
}
if (idx == n) return s;
string x = s.substr(idx, n - idx);
reverse(x.begin(), x.end());
return x + s;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func shortestPalindrome(s string) string {
n := len(s)
base, mod := 131, int(1e9)+7
prefix, suffix, mul := 0, 0, 1
idx := 0
for i, c := range s {
t := int(c-'a') + 1
prefix = (prefix*base + t) % mod
suffix = (suffix + t*mul) % mod
mul = (mul * base) % mod
if prefix == suffix {
idx = i + 1
}
}
if idx == n {
return s
}
x := []byte(s[idx:])
for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
x[i], x[j] = x[j], x[i]
}
return string(x) + s
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| impl Solution {
pub fn shortest_palindrome(s: String) -> String {
let base = 131;
let (mut idx, mut prefix, mut suffix, mut mul) = (0, 0, 0, 1);
for (i, c) in s.chars().enumerate() {
let t = (c as u64) - ('0' as u64) + 1;
prefix = prefix * base + t;
suffix = suffix + t * mul;
mul *= base;
if prefix == suffix {
idx = i + 1;
}
}
if idx == s.len() {
s
} else {
let x: String = (&s[idx..]).chars().rev().collect();
String::from(x + &s)
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| // https://leetcode.com/problems/shortest-palindrome/
using System.Text;
public partial class Solution
{
public string ShortestPalindrome(string s)
{
for (var i = s.Length - 1; i >= 0; --i)
{
var k = i;
var j = 0;
while (j < k)
{
if (s[j] == s[k])
{
++j;
--k;
}
else
{
break;
}
}
if (j >= k)
{
var sb = new StringBuilder(s.Length * 2 - i - 1);
for (var l = s.Length - 1; l >= i + 1; --l)
{
sb.Append(s[l]);
}
sb.Append(s);
return sb.ToString();
}
}
return string.Empty;
}
}
|
