String
String Matching
Hash Function
Rolling Hash
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 * 104
s
consists of lowercase English letters only.
Solutions
Solution 1
Python3 Java C++ Go Rust C#
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 public class Solution {
public string ShortestPalindrome ( string s ) {
int baseValue = 131 ;
int mul = 1 ;
int mod = ( int ) 1 e9 + 7 ;
int prefix = 0 , suffix = 0 ;
int idx = 0 ;
int n = s . Length ;
for ( int i = 0 ; i < n ; ++ i ) {
int t = s [ i ] - 'a' + 1 ;
prefix = ( int )((( long ) prefix * baseValue + t ) % mod );
suffix = ( int )(( suffix + ( long ) t * mul ) % mod );
mul = ( int )((( long ) mul * baseValue ) % mod );
if ( prefix == suffix ) {
idx = i + 1 ;
}
}
if ( idx == n ) {
return s ;
}
return new string ( s . Substring ( idx ). Reverse (). ToArray ()) + s ;
}
}
Solution 2: KMP Algorithm
According to the problem description, we need to reverse the string $s$ to obtain the string $\textit{rev}$, and then find the longest common part of the suffix of the string $\textit{rev}$ and the prefix of the string $s$. We can use the KMP algorithm to concatenate the string $s$ and the string $\textit{rev}$ and find the longest common part of the longest prefix and the longest suffix.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$.
Python3 Java C++ Go TypeScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def shortestPalindrome ( self , s : str ) -> str :
t = s + "#" + s [:: - 1 ] + "$"
n = len ( t )
next = [ 0 ] * n
next [ 0 ] = - 1
i , j = 2 , 0
while i < n :
if t [ i - 1 ] == t [ j ]:
j += 1
next [ i ] = j
i += 1
elif j :
j = next [ j ]
else :
next [ i ] = 0
i += 1
return s [:: - 1 ][: - next [ - 1 ]] + s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public String shortestPalindrome ( String s ) {
String rev = new StringBuilder ( s ). reverse (). toString ();
char [] t = ( s + "#" + rev + "$" ). toCharArray ();
int n = t . length ;
int [] next = new int [ n ] ;
next [ 0 ] = - 1 ;
for ( int i = 2 , j = 0 ; i < n ;) {
if ( t [ i - 1 ] == t [ j ] ) {
next [ i ++] = ++ j ;
} else if ( j > 0 ) {
j = next [ j ] ;
} else {
next [ i ++] = 0 ;
}
}
return rev . substring ( 0 , s . length () - next [ n - 1 ] ) + s ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
string shortestPalindrome ( string s ) {
string t = s + "#" + string ( s . rbegin (), s . rend ()) + "$" ;
int n = t . size ();
int next [ n ];
next [ 0 ] = -1 ;
next [ 1 ] = 0 ;
for ( int i = 2 , j = 0 ; i < n ;) {
if ( t [ i - 1 ] == t [ j ]) {
next [ i ++ ] = ++ j ;
} else if ( j > 0 ) {
j = next [ j ];
} else {
next [ i ++ ] = 0 ;
}
}
return string ( s . rbegin (), s . rbegin () + s . size () - next [ n - 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
24
25
26
27 func shortestPalindrome ( s string ) string {
t := s + "#" + reverse ( s ) + "$"
n := len ( t )
next := make ([] int , n )
next [ 0 ] = - 1
for i , j := 2 , 0 ; i < n ; {
if t [ i - 1 ] == t [ j ] {
j ++
next [ i ] = j
i ++
} else if j > 0 {
j = next [ j ]
} else {
next [ i ] = 0
i ++
}
}
return reverse ( s )[: len ( s ) - next [ n - 1 ]] + s
}
func reverse ( s string ) string {
t := [] byte ( s )
for i , j := 0 , len ( t ) - 1 ; i < j ; i , j = i + 1 , j - 1 {
t [ i ], t [ j ] = t [ j ], t [ i ]
}
return string ( t )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 function shortestPalindrome ( s : string ) : string {
const rev = s . split ( '' ). reverse (). join ( '' );
const t = s + '#' + rev + '$' ;
const n = t . length ;
const next : number [] = Array ( n ). fill ( 0 );
next [ 0 ] = - 1 ;
for ( let i = 2 , j = 0 ; i < n ; ) {
if ( t [ i - 1 ] === t [ j ]) {
next [ i ++ ] = ++ j ;
} else if ( j > 0 ) {
j = next [ j ];
} else {
next [ i ++ ] = 0 ;
}
}
return rev . slice ( 0 , - next [ n - 1 ]) + s ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 public class Solution {
public string ShortestPalindrome ( string s ) {
char [] t = ( s + "#" + new string ( s . Reverse (). ToArray ()) + "$" ). ToCharArray ();
int n = t . Length ;
int [] next = new int [ n ];
next [ 0 ] = - 1 ;
for ( int i = 2 , j = 0 ; i < n ;) {
if ( t [ i - 1 ] == t [ j ]) {
next [ i ++ ] = ++ j ;
} else if ( j > 0 ) {
j = next [ j ];
} else {
next [ i ++ ] = 0 ;
}
}
return new string ( s . Substring ( next [ n - 1 ]). Reverse (). ToArray ()). Substring ( 0 , s . Length - next [ n - 1 ]) + s ;
}
}
GitHub