难度困难
题目描述
给定一个由唯一字符串构成的 0 索引 数组 words 。
回文对 是一对整数 (i, j) ，满足以下条件：
0 <= i, j < words.length，i != j ，并且words[i] + words[j]（两个字符串的连接）是一个回文串。
返回一个数组，它包含 words 中所有满足 回文对 条件的字符串。
你必须设计一个时间复杂度为 O(sum of words[i].length) 的算法。
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]
提示：
1 <= words.length <= 50000 <= words[i].length <= 300words[i] 由小写英文字母组成
解法
方法一：哈希表
思考
两词拼接为回文。若枚举所有有序对再检测，词数与长度乘积过大。把一词切开，若一侧已是回文，则另一侧的逆串若在词表中即可配对。
哈希表记下每个词的下标。对 \(w\) 的每个切点，前缀为回文则找后缀逆，后缀为回文则找前缀逆；切点 \(j=0\) 只计一侧以免空串重复。代码按切点同时检查两侧。
用哈希表记下每个单词的下标。枚举单词 \(w\) 的切分位置 \(j\)，记前缀 \(a=w[:j]\)、后缀 \(b=w[j:]\)。
- 若后缀 \(b\) 是回文，且前缀 \(a\) 的逆序串在哈希表中，则该逆序串接在 \(w\) 左侧后构成回文。
- 若 \(j>0\) 且前缀 \(a\) 是回文，且后缀 \(b\) 的逆序串在哈希表中，则该逆序串接在 \(w\) 右侧后构成回文。 \(j=0\) 时前缀为空，不再从这一侧配对，避免空串被重复统计。
时间复杂度 \(O(\sum |w_i|^2)\)，空间复杂度 \(O(\sum |w_i|)\)。
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 | class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> d = new HashMap<>();
for (int i = 0; i < words.length; ++i) {
d.put(words[i], i);
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < words.length; ++i) {
String w = words[i];
int m = w.length();
for (int j = 0; j <= m; ++j) {
String a = w.substring(0, j);
String b = w.substring(j);
String ra = new StringBuilder(a).reverse().toString();
String rb = new StringBuilder(b).reverse().toString();
if (d.containsKey(ra) && d.get(ra) != i && b.equals(rb)) {
ans.add(Arrays.asList(i, d.get(ra)));
}
if (j > 0 && d.containsKey(rb) && d.get(rb) != i && a.equals(ra)) {
ans.add(Arrays.asList(d.get(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 | func palindromePairs(words []string) [][]int {
d := map[string]int{}
for i, w := range words {
d[w] = i
}
var ans [][]int
for i, w := range words {
for j := 0; j <= len(w); j++ {
a, b := w[:j], w[j:]
ra, rb := reverse(a), reverse(b)
if k, ok := d[ra]; ok && k != i && b == rb {
ans = append(ans, []int{i, k})
}
if j > 0 {
if k, ok := d[rb]; ok && k != i && a == ra {
ans = append(ans, []int{k, i})
}
}
}
}
return ans
}
func reverse(s string) string {
b := []byte(s)
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
return string(b)
}
|
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 | 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;
}
}
|
方法二：前缀树
思考
方法一对每个切点在哈希表中查完整逆串。把词插入前缀树后，可沿另一词反向走字符，在结点处读取下标，避免每次构造整段逆串。后缀（前缀）为回文时在对应深度取树中词号，语义与方法一相同。
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;
}
}
|