Welcome to Subscribe On Youtube
336. Palindrome Pairs
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: Direct Implementation
String hash maps a string of any length into a non-negative integer, and the probability of collision is almost $0$. String hashing is used to calculate string hash values and quickly determine whether two strings are equal.
Take a fixed value $BASE$, treat the string as a $BASE$ base number, and assign a value greater than $0$ to represent each character. Generally speaking, the values we assign are much smaller than $BASE$. For example, for a string of lowercase letters, $a=1$, $b=2$, …, $z=26$. Take a fixed value $MOD$ and find the remainder of the $BASE$ base pair $M$ as the $hash$ value of the string.
Generally speaking, take $BASE=131$ or $BASE=13331$. At this time, the probability of conflict caused by the $hash$ value is extremely low. As long as the two strings have the same $hash$ value, we consider the two strings to be equal. Usually $MOD$ takes $2^{64}$. In C++, you can directly use the unsigned long long type to store the $hash$ value. The arithmetic overflow problem is not dealt with during calculation. When overflow occurs, it is equivalent to automatically taking the modulo $2^{64}$, which can avoid inefficient modulo operations.
Except for very specially structured data, the above-mentioned $hash$ algorithm is difficult to conflict. In general, the above-mentioned $hash$ algorithm can appear in the standard answer to the question. We can also take more appropriate $BASE$ and $MOD$ values (such as large prime numbers) and perform several more sets of $hash$ operations. When the results are the same, the original strings are considered equal. It will be more difficult to construct data that causes this $hash$ to produce errors.
Solution 2
This implementation uses bit manipulation. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.
-
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; } } // Solution 2 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; } } -
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 -
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 } -
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; } }