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, andwords[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 <= 50000 <= words[i].length <= 300words[i] consists of lowercase English letters.
Solutions
Solution 1
PythonJavaGoC#
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(code-box)
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;
}
}(code-box)
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
}(code-box)
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;
}
}(code-box)
Solution 2
Java
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;
}
}(code-box)
