给定一个由唯一字符串构成的 **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] 由小写英文字母组成
方法一：简单的暴力[超时]
分析：
- 简单的暴力枚举出所有的字符串对，然后判断它们组成的字符串是否是回文对
- 时间复杂度为：$O(NNK)$ 其中，$N$ 为
words 列表的长度，$K$ 为每个单词的平均长度
- 当数据量较大时，超时
实现：
[]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ans = new ArrayList<>();
int n = words.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (!check(words[i]+words[j])) continue;
List<Integer> temp = new ArrayList<>();
temp.add(i); temp.add(j);
ans.add(temp);
}
}
return ans;
}
private boolean check(String s) {
int i = 0, j = s.length()-1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) return false;
i++; j--;
}
return true;
}
}
|
方法二：字典树（Trie树）[通过]
分析：
- 根据回文字符串的性质，我们可以不用暴力枚举出所有字符串对
- 对于一个字符串对 $(x, y)$, 若想要字符串 $x+y$ 是一个回文字符串，则必须满足以下条件之一
- 当 $x.length() \geq y.length()$ 时, 字符串 $x$ 的 $y.length()$ 长度的前缀与 $y$ 的 逆序 相等，且字符串 $x$ 去除长度为 $y.length()$ 的前缀后，余下的部分也是一个回文字符串。
- 当 $x.length() < y.length()$ 时，与情况一正相反。
{:width=300}
- 对于字符串 $x$ 时，我们依次遍历其每一个字母，假设当前遍历到的位置为 $i$,若 $[i,x.length()]$ 是一个回文对，且 $[0,i]$ 的逆序存在于 $word$ 列表中（设其下标为 $y$），则 $(x, y)$ 可以构成回文对，加入结果数组中。
- 当我们遍历完字符串 $x$ 的每一个字符，我们还 需要考虑分析中第2种情况，即 $x.length() < y.length()$
- 为了加快查找速率，我们利用字典树辅助查找，其中重要的是字典树每一个
Node 里所保存的信息。
- 1.
List<Integer> words 存储以当前节点为终止节点的所有单词（逆序之后的),来获取所有第1种情况下的匹配成功的字符串 $y$
- 2.
List<Integer> suffixs 保存所有到当前节点为止，其之后剩余字符可以构成回文对的单词。用来获取所有长度大于 $x.length()$，且可以和其构成回文对的单词 $y$（即针对第二种情况）。
代码实现：
- 用每个单词的逆序构建字典树
- 在每个节点上维护以该节点为终止节点的单词
- 在若在该节点之和的部分能构成回文对，则加入 suffixs 列表中。
- 详情见注释
[]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
| class Solution {
private Node root;
public List<List<Integer>> palindromePairs(String[] words) {
this.root = new Node();
int n = words.length;
for (int i = 0; i < n; i++) {
String rev = new StringBuilder(words[i]).reverse().toString();
Node cur = root;
if (isPalindrome(rev.substring(0))) cur.suffixs.add(i);
for (int j = 0; j < rev.length(); j++) {
char ch = rev.charAt(j);
if (cur.children[ch-'a']==null) cur.children[ch-'a'] = new Node();
cur = cur.children[ch-'a'];
if (isPalindrome(rev.substring(j+1))) cur.suffixs.add(i);
}
cur.words.add(i);
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
String word = words[i];
Node cur = root;
int j = 0;
for ( ;j < word.length(); j++) {
if(isPalindrome(word.substring(j)))
for (int k : cur.words)
if (k != i) ans.add(Arrays.asList(i,k));
char ch = word.charAt(j);
if (cur.children[ch-'a'] == null) break;
cur = cur.children[ch-'a'];
}
if (j == word.length())
for (int k : cur.suffixs)
if (k != i) ans.add(Arrays.asList(i,k));
}
return ans;
}
private boolean isPalindrome(String w) {
int i = 0, j = w.length()-1;
while (i < j) {
if (w.charAt(i) != w.charAt(j)) return false;
i++; j--;
}
return true;
}
}
class Node {
public Node[] children;
public List<Integer> words;
public List<Integer> suffixs;
public Node() {
this.children = new Node[26];
this.words = new ArrayList<>();
this.suffixs = new ArrayList<>();
}
}
|
复杂度分析
时间复杂度 ：$O(N*K^2)$ 其中 $N$ 为列表长度，$K$ 为每个单词平均长度。
{:width=300}