leetcode 336 Palindrome Pairs

不念不忘少年蓝@ 2021-11-29 15:44 167阅读 0赞

lc 336 Palindrome Pairs

![794462-20190621095920532-894521183.png][]

最简单的就是每两个都拼接一下，然后判断是否为回文串

时间复杂度为o(n^2\*k) n：words个数 k：word平均长度

但是我们仔细观察一下，两个word拼接之后，是如何判断是否为回文串的呢？首尾指针，匹配，向中间收缩。

假如现在有一个单词"asad"，有可能和它组成回文串的字母一定结尾是a，"???????a"，倒数第二个字母一定是s，这样不就减少无效的比对，从而减少时间复杂度了吗？

但是如何实现呢？

这里用到trie的思想

root为空

子节点为a~z

迭代向下

每一个叶子节点向上到达root节点的路径，一定能构成原数组中的一个word

举例说明

数组：\["asad", "ascc", "azlp"\]

root

s　　　　　　z

a　　c　　　 l

d　　c　　　 p

这样一个数据结构可以满足我们上述思路的要求

只需要遍历一次原数组，依次检查words\[i\]，找出能和它组成回文串的word

实现时，注意要从words尾部开始构建trie树，上面的例子是从头开始的，反了

能组成回文串有三种情况

word A & word B

1.A和B等长

那么只需要一直从root往下走（一个for循环，i=0，i<A.length()）走A步，都能匹配上，说明AB能组成回文串

举例来说，

原数组为:\["asad", "dasa"\]tire树为

a　　d

s　　a

a　　s

d　　a

我们首先检查words\[0\] : "asad"

root->a节点 找到

\->s节点 找到

\->a节点 找到

\->d节点 找到

匹配成功 0,1可以组成回文串

2.A>B

A:"asadgg"

B:"dasa

"asad"匹配完毕，但是匹配到g时，后面没有节点了

这个时候，就需要检查A在"asad"之后的子串是否为回文串

若是，则asad + 子串 + dasa肯定能构成回文串

3.A<B

A:"asad"

B:"dasagg"

"asad"匹配完毕，但是到d就截止了，因为我们的for循环是以A的长度为止的

那么就需要检查B串"dasa"之后的子串是否为回文串了

结论同上，不过这里有个小方法，可以在自建trieNode类中加一个isP\[\]数组，用来记录之后子串为回文串的单词索引，避免了每次都要重新比较

1 class Solution {
     2     private static class trieNode{
     3         trieNode[] next;
     4         int index;
     5         List<Integer> isP;
     6         
     7         trieNode(){
     8             next = new trieNode[26];
     9             index = -1;
    10             isP = new ArrayList<Integer>();
    11         }
    12         
    13     }
    14     public List<List<Integer>> palindromePairs(String[] words) {
    15         List<List<Integer>> res = new ArrayList<>();
    16         trieNode root = new trieNode();
    17         
    18         for(int i=0; i<words.length; i++){
    19             addWord(root, words[i], i);
    20         }
    21         
    22         for(int i=0; i<words.length; i++){
    23             search(res, root, words[i], i);
    24         }
    25         return res;
    26     }
    27     
    28     private void addWord(trieNode root, String s, int index){
    29         for(int i=s.length()-1; i>=0; i--){
    30             int j = s.charAt(i)-'a';
    31             if(root.next[j] == null){
    32                 root.next[j] = new trieNode();
    33             }
    34             if(laterIsP(s, 0, i)){
    35                 root.isP.add(index);
    36             }
    37             
    38             root = root.next[j];
    39             
    40         }
    41         root.isP.add(index);
    42         root.index = index;
    43     }
    44     
    45     private boolean laterIsP(String s, int i, int j){
    46         while(i < j){
    47             if(s.charAt(i++) != s.charAt(j--))
    48                 return false;
    49         }
    50         
    51         return true;
    52     }
    53     
    54     private void search(List<List<Integer>> res, trieNode root, String s, int index){
    55         for(int i=0; i<s.length(); i++){
    56             if(root.index >= 0 && index != root.index && laterIsP(s, i, s.length()-1)){
    57                 res.add(Arrays.asList(index, root.index)); 
    58             }
    59             root = root.next[s.charAt(i)-'a'];
    60             if(root == null)
    61                 return;
    62                 
    63         }
    64         
    65         for(int i : root.isP){
    66             if(i != index)
    67                 res.add(Arrays.asList(index, i));
    68         }
    69     }
    70 }

转载于:https://www.cnblogs.com/hwd9654/p/11063153.html

[794462-20190621095920532-894521183.png]: /images/20211129/5d75d998217242a1b13d43fa8d8209f4.png