336 Palindrome Pairs

Search…
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)
211 Add and Search Word - Data structure design
421 Maximum XOR of Two Numbers in an Array
Last modified 2yr ago
Copy link
Contents
336. Palindrome Pairs
1. Question
2. Implementation
3. Time & Space Complexity
336. Palindrome Pairs​

1. Question

2. Implementation

3. Time & Space Complexity

336. Palindrome Pairs
