Trie
Array
Hash Table
String
Description
You are given a 0-indexed array of unique strings words
.
A palindrome pair is a pair of integers (i, j)
such that:
0 <= i, j < words.length
,
i != j
, and
words[i] + words[j]
(the concatenation of the two strings) is a palindrome .
Return an array of all the palindrome pairs of words
.
You must write an algorithm with O(sum of words[i].length)
runtime complexity.
Example 1:
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
Example 2:
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
Example 3:
Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]
Constraints:
1 <= words.length <= 5000
0 <= words[i].length <= 300
words[i]
consists of lowercase English letters.
Solutions
Solution 1
Python3 Java Go C#
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def palindromePairs ( self , words : List [ str ]) -> List [ List [ int ]]:
d = { w : i for i , w in enumerate ( words )}
ans = []
for i , w in enumerate ( words ):
for j in range ( len ( w ) + 1 ):
a , b = w [: j ], w [ j :]
ra , rb = a [:: - 1 ], b [:: - 1 ]
if ra in d and d [ ra ] != i and b == rb :
ans . append ([ i , d [ ra ]])
if j and rb in d and d [ rb ] != i and a == ra :
ans . append ([ d [ rb ], i ])
return ans
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
40
41
42
43
44 class Solution {
private static final int BASE = 131 ;
private static final long [] MUL = new long [ 310 ] ;
private static final int MOD = ( int ) 1e9 + 7 ;
static {
MUL [ 0 ] = 1 ;
for ( int i = 1 ; i < MUL . length ; ++ i ) {
MUL [ i ] = ( MUL [ i - 1 ] * BASE ) % MOD ;
}
}
public List < List < Integer >> palindromePairs ( String [] words ) {
int n = words . length ;
long [] prefix = new long [ n ] ;
long [] suffix = new long [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
String word = words [ i ] ;
int m = word . length ();
for ( int j = 0 ; j < m ; ++ j ) {
int t = word . charAt ( j ) - 'a' + 1 ;
int s = word . charAt ( m - j - 1 ) - 'a' + 1 ;
prefix [ i ] = ( prefix [ i ] * BASE ) % MOD + t ;
suffix [ i ] = ( suffix [ i ] * BASE ) % MOD + s ;
}
}
List < List < Integer >> ans = new ArrayList <> ();
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
if ( check ( i , j , words [ j ] . length (), words [ i ] . length (), prefix , suffix )) {
ans . add ( Arrays . asList ( i , j ));
}
if ( check ( j , i , words [ i ] . length (), words [ j ] . length (), prefix , suffix )) {
ans . add ( Arrays . asList ( j , i ));
}
}
}
return ans ;
}
private boolean check ( int i , int j , int n , int m , long [] prefix , long [] suffix ) {
long t = (( prefix [ i ] * MUL [ n ] ) % MOD + prefix [ j ] ) % MOD ;
long s = (( suffix [ j ] * MUL [ m ] ) % MOD + suffix [ i ] ) % MOD ;
return t == 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 func palindromePairs ( words [] string ) [][] int {
base := 131
mod := int ( 1e9 ) + 7
mul := make ([] int , 310 )
mul [ 0 ] = 1
for i := 1 ; i < len ( mul ); i ++ {
mul [ i ] = ( mul [ i - 1 ] * base ) % mod
}
n := len ( words )
prefix := make ([] int , n )
suffix := make ([] int , n )
for i , word := range words {
m := len ( word )
for j , c := range word {
t := int ( c - 'a' ) + 1
s := int ( word [ m - j - 1 ] - 'a' ) + 1
prefix [ i ] = ( prefix [ i ] * base ) % mod + t
suffix [ i ] = ( suffix [ i ] * base ) % mod + s
}
}
check := func ( i , j , n , m int ) bool {
t := (( prefix [ i ] * mul [ n ]) % mod + prefix [ j ]) % mod
s := (( suffix [ j ] * mul [ m ]) % mod + suffix [ i ]) % mod
return t == s
}
var ans [][] int
for i := 0 ; i < n ; i ++ {
for j := i + 1 ; j < n ; j ++ {
if check ( i , j , len ( words [ j ]), len ( words [ i ])) {
ans = append ( ans , [] int { i , j })
}
if check ( j , i , len ( words [ i ]), len ( words [ j ])) {
ans = append ( ans , [] int { j , i })
}
}
}
return ans
}
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
40
41
42
43
44
45
46
47
48
49
50 using System.Collections.Generic ;
using System.Linq ;
public class Solution {
public IList < IList < int >> PalindromePairs ( string [] words ) {
var results = new List < IList < int >> ();
var reverseDict = words . Select (( w , i ) => new { Word = w , Index = i }). ToDictionary ( w => new string ( w . Word . Reverse (). ToArray ()), w => w . Index );
for ( var i = 0 ; i < words . Length ; ++ i )
{
var word = words [ i ];
for ( var j = 0 ; j <= word . Length ; ++ j )
{
if ( j > 0 && IsPalindrome ( word , 0 , j - 1 ))
{
var suffix = word . Substring ( j );
int pairIndex ;
if ( reverseDict . TryGetValue ( suffix , out pairIndex ) && i != pairIndex )
{
results . Add ( new [] { pairIndex , i });
}
}
if ( IsPalindrome ( word , j , word . Length - 1 ))
{
var prefix = word . Substring ( 0 , j );
int pairIndex ;
if ( reverseDict . TryGetValue ( prefix , out pairIndex ) && i != pairIndex )
{
results . Add ( new [] { i , pairIndex });
}
}
}
}
return results ;
}
private bool IsPalindrome ( string word , int startIndex , int endIndex )
{
var i = startIndex ;
var j = endIndex ;
while ( i < j )
{
if ( word [ i ] != word [ j ]) return false ;
++ i ;
-- j ;
}
return true ;
}
}
Solution 2
Java
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 class Trie {
Trie [] children = new Trie [ 26 ] ;
Integer v ;
void insert ( String w , int i ) {
Trie node = this ;
for ( char c : w . toCharArray ()) {
c -= 'a' ;
if ( node . children [ c ] == null ) {
node . children [ c ] = new Trie ();
}
node = node . children [ c ] ;
}
node . v = i ;
}
Integer search ( String w , int i , int j ) {
Trie node = this ;
for ( int k = j ; k >= i ; -- k ) {
int idx = w . charAt ( k ) - 'a' ;
if ( node . children [ idx ] == null ) {
return null ;
}
node = node . children [ idx ] ;
}
return node . v ;
}
}
class Solution {
public List < List < Integer >> palindromePairs ( String [] words ) {
Trie trie = new Trie ();
int n = words . length ;
for ( int i = 0 ; i < n ; ++ i ) {
trie . insert ( words [ i ] , i );
}
List < List < Integer >> ans = new ArrayList <> ();
for ( int i = 0 ; i < n ; ++ i ) {
String w = words [ i ] ;
int m = w . length ();
for ( int j = 0 ; j <= m ; ++ j ) {
if ( isPalindrome ( w , j , m - 1 )) {
Integer k = trie . search ( w , 0 , j - 1 );
if ( k != null && k != i ) {
ans . add ( Arrays . asList ( i , k ));
}
}
if ( j != 0 && isPalindrome ( w , 0 , j - 1 )) {
Integer k = trie . search ( w , j , m - 1 );
if ( k != null && k != i ) {
ans . add ( Arrays . asList ( k , i ));
}
}
}
}
return ans ;
}
// TLE
// private boolean isPalindrome(String w, int i, int j) {
// for (; i < j; ++i, --j) {
// if (w.charAt(i) != w.charAt(j)) {
// return false;
// }
// }
// return true;
// }
private boolean isPalindrome ( String w , int start , int end ) {
int i = start , j = end ;
for (; i < j ; ++ i , -- j ) {
if ( w . charAt ( i ) != w . charAt ( j )) {
return false ;
}
}
return true ;
}
}
GitHub