336 Palindrome Pairs

1. Question

Given a list of unique words, find all pairs of distinct indices(i, j)in the given list, so that the concatenation of the two words, i.e.words[i] + words[j]is a palindrome.
Example 1: Givenwords=["bat", "tab", "cat"] Return[[0, 1], [1, 0]] The palindromes are["battab", "tabbat"] Example 2: Givenwords=["abcd", "dcba", "lls", "s", "sssll"] Return[[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are["dcbaabcd", "abcddcba", "slls", "llssssll"]

2. Implementation

(1) Trie
思路:
(1) 要看两个string连在一起是否回文串,那么这两个string必然满足这样的性质:一个string的前缀和另一个string的后缀相同且除去前(后)缀的剩余是回文串(包括空字符串)。
(2)为了比较不同string的前后缀,我们可以利用trie,插入时将每个word按照倒序放入trie,这样的好处是,当我们查询一个string的前缀时,可以通过trie快速的找到有没与前缀相同的后缀
(3)对于子串中存在回文串的string(包括空字符串), 比如abac中有aba这个回文子串,我们在trieNode里维护一个list,保存这种特性的word在输入数组的index
1
class Solution {
2
class TrieNode {
3
//记录word在输入数组的index, 预设值为-1
4
int index;
5
// 保存word在输入数组的index,这种word满足条件:
6
// word的后缀在trie里, 剩余部分是回文串(包括空串)。比如abac, c为后缀,剩余部分aba。注意abac是倒着插入(即caba)trie的
7
List<Integer> list;
8
TrieNode[] childNode;
9
10
public TrieNode() {
11
index = -1;
12
list = new ArrayList<>();
13
childNode = new TrieNode[26];
14
}
15
}
16
17
class Trie {
18
TrieNode root;
19
20
public Trie() {
21
root = new TrieNode();
22
}
23
24
// 将Word倒序的插入Trie里
25
public void insert(String word, int index) {
26
TrieNode curNode = root;
27
28
for (int i = word.length() - 1; i >= 0; i--) {
29
if (isPalindrome(word, 0, i)) {
30
curNode.list.add(index);
31
}
32
33
int pos = word.charAt(i) - 'a';
34
35
if (curNode.childNode[pos] == null) {
36
curNode.childNode[pos] = new TrieNode();
37
}
38
curNode = curNode.childNode[pos];
39
}
40
curNode.index = index;
41
curNode.list.add(index);
42
}
43
44
public void search(String word, int index, List<List<Integer>> res) {
45
TrieNode curNode = root;
46
47
for (int i = 0; i < word.length(); i++) {
48
// curNode.index >= 0 意味着这里有输入数组里的string
49
// curNode.index != index 说明curNode.index对应的string和index对应的string不同
50
// 当word[i...word.length() - 1]是回文串时,说明curNode.index对应的string和index对应的string可以连在一起形成回文串
51
if (curNode.index >= 0 && curNode.index != index && isPalindrome(word, i, word.length() - 1)) {
52
res.add(Arrays.asList(index, curNode.index));
53
}
54
55
int pos = word.charAt(i) - 'a';
56
57
if (curNode.childNode[pos] == null) {
58
return;
59
}
60
curNode = curNode.childNode[pos];
61
}
62
63
// 当word在字符串中找到与它相同的string后, 查看curNode.list里的index, 这些index对应的word都是在curNode后面的substring为回文串
64
for (int j : curNode.list) {
65
if (j != index) {
66
res.add(Arrays.asList(index, j));
67
}
68
}
69
}
70
}
71
72
public List<List<Integer>> palindromePairs(String[] words) {
73
List<List<Integer>> res = new ArrayList<>();
74
75
if (words == null || words.length == 0) {
76
return res;
77
}
78
79
Trie trie = new Trie();
80
81
for (int i = 0; i < words.length; i++) {
82
trie.insert(words[i], i);
83
}
84
85
for (int i = 0; i < words.length; i++) {
86
trie.search(words[i], i, res);
87
}
88
return res;
89
}
90
91
public boolean isPalindrome(String word, int start, int end) {
92
while (start < end) {
93
if (word.charAt(start) != word.charAt(end)) {
94
return false;
95
}
96
++start;
97
--end;
98
}
99
return true;
100
}
101
}
Copied!

3. Time & Space Complexity

Trie: 时间复杂度O(nL^2),n是words里的元素个数,L是words里word的平均长度。空间复杂度O(nL)