0%

leetcode每日一题-回文对

Posted on In ,

回文对

image1

暴力方法就是枚举每一对字符串的组合，暴力判断它们是否能够构成回文串即可。但时间复杂度太高，需要进行优化。

方法一：枚举前缀和后缀

考虑两个字符串$s1$和$s2$，如果两个字符串能组成回文字符串，那么有三种情况：

  1. $len1==len2$，那么只需要判断$s1+s2$是否是回文字符串即可
  2. $len1>len2$，那么$s1$分为两部分$t1$和$t2$，其中$t2$是回文字符串，$t1$是$s2$的翻转，那么$s1+s2$也就是$t1+t2+s2$就能组成回文字符串。
  3. $len1<len2$，那么$s2$分为两部分$t1$和$t2$，其中$t1$是回文字符串，$t2$是$s1$的翻转，那么那么$s1+s2$也就是$s1+t1+t2$就能组成回文字符串。

算法流程如下：

  1. 枚举每个字符串
  2. 检查字符串的前缀和后缀是否存在回文子串
  3. 如果存在，查找字符串的剩余部分的翻转形式是否存在

其中查找字符串的剩余部分的翻转形式是否存在可以使用字典树或者哈希表来存储。

这是用字典树实现的：

1
class Solution {
2
    Trie trie;
3
    public List<List<Integer>> palindromePairs(String[] words) {
4
        trie = new Trie();
5
        int n = words.length;
6
        for(int i=0; i<n; i++){
7
            trie.insert(words[i], i);
8
        }
9
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
10
        for(int i=0; i<n; i++){
11
            int m = words[i].length();
12
            for(int j=0; j<=m; j++){
13
                if(isPalindromePairs(words[i], j, m-1)){
14
                    int leftId = findWord(words[i], 0, j-1);
15
                    if(leftId != -1 && leftId != i){
16
                        ret.add(Arrays.asList(i, leftId));
17
                    }
18
                }
19
                if(j!=0 && isPalindromePairs(words[i], 0, j-1)){
20
                    int rightId = findWord(words[i], j, m-1);
21
                    if(rightId != -1 && rightId != i){
22
                        ret.add(Arrays.asList(rightId, i));
23
                    }
24
                }
25
            }
26
        }
27
        return ret;
28
    }
29
30
    public boolean isPalindromePairs(String word, int left, int right){
31
        int len = right-left+1;
32
        for(int i=0; i<len/2; i++){
33
            if(word.charAt(left+i) != word.charAt(right-i)){
34
                return false;
35
            }
36
        }
37
        return true;
38
    }
39
40
    public int findWord(String s, int left, int right){
41
        String reversed = new StringBuffer(s.substring(left, right+1)).reverse().toString();
42
        int len = right - left + 1;
43
        TrieNode node = trie.searchPrefix(reversed);
44
        if(node == null){
45
            return -1;
46
        }
47
        return node.getFlag();
48
    }
49
}
50
51
class Trie {
52
53
    private TrieNode root;
54
55
    /** Initialize your data structure here. */
56
    public Trie() {
57
        root = new TrieNode();
58
    }
59
    
60
    /** Inserts a word into the trie. */
61
    public void insert(String word, int flag) {
62
        TrieNode node =root;
63
        for(int i=0; i<word.length(); i++){
64
            char currentChar = word.charAt(i);
65
            if(!node.containsKey(currentChar)){
66
                node.put(new TrieNode(), currentChar);
67
            }
68
            node = node.get(currentChar);
69
        }
70
        node.setEnd();
71
        node.setFlag(flag);
72
    }
73
74
    public TrieNode searchPrefix(String word){
75
        TrieNode node = root;
76
        for(int i=0; i<word.length(); i++){
77
            char currentChar = word.charAt(i);
78
            if(node.containsKey(currentChar)){
79
                node = node.get(currentChar);
80
            }else{
81
                return null;
82
            }
83
        }
84
        return node;
85
    }
86
    
87
    /** Returns if the word is in the trie. */
88
    public boolean search(String word) {
89
        TrieNode node = searchPrefix(word);
90
        return node!=null && node.isEnd();
91
    }
92
    
93
    /** Returns if there is any word in the trie that starts with the given prefix. */
94
    public boolean startsWith(String prefix) {
95
        TrieNode node = searchPrefix(prefix);
96
        return node!=null;
97
    }
98
}
99
100
class TrieNode{
101
    // R links to node children
102
    private TrieNode[] links;
103
    private final int R = 26;
104
    private boolean isEnd;
105
    private int flag;
106
    public TrieNode(){
107
        links = new TrieNode[R];
108
        flag = -1;
109
    }
110
111
    public boolean containsKey(char ch){
112
        return links[ch - 'a'] != null;
113
    }
114
115
    public TrieNode get(char ch){
116
        return links[ch - 'a'];
117
    }
118
119
    public void put(TrieNode node, char ch){
120
        links[ch - 'a'] = node;
121
    }
122
123
    public void setEnd(){
124
        isEnd = true;
125
    }
126
127
    public boolean isEnd(){
128
        return isEnd;
129
    }
130
131
    public void setFlag(int flag){
132
        this.flag = flag;
133
    }
134
135
    public int getFlag(){
136
        return flag;
137
    }
138
}

这是用哈希表实现的：

1
class Solution {
2
    List<String> wordsRev = new ArrayList<String>();
3
    Map<String, Integer> indices = new HashMap<String, Integer>();
4
5
    public List<List<Integer>> palindromePairs(String[] words) {
6
        int n = words.length;
7
        for (String word: words) {
8
            wordsRev.add(new StringBuffer(word).reverse().toString());
9
        }
10
        for (int i = 0; i < n; ++i) {
11
            indices.put(wordsRev.get(i), i);
12
        }
13
14
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
15
        for (int i = 0; i < n; i++) {
16
            String word = words[i];
17
            int m = words[i].length();
18
            if (m == 0) {
19
                continue;
20
            }
21
            for (int j = 0; j <= m; j++) {
22
                if (isPalindrome(word, j, m - 1)) {
23
                    int leftId = findWord(word, 0, j - 1);
24
                    if (leftId != -1 && leftId != i) {
25
                        ret.add(Arrays.asList(i, leftId));
26
                    }
27
                }
28
                if (j != 0 && isPalindrome(word, 0, j - 1)) {
29
                    int rightId = findWord(word, j, m - 1);
30
                    if (rightId != -1 && rightId != i) {
31
                        ret.add(Arrays.asList(rightId, i));
32
                    }
33
                }
34
            }
35
        }
36
        return ret;
37
    }
38
39
    public boolean isPalindrome(String s, int left, int right) {
40
        int len = right - left + 1;
41
        for (int i = 0; i < len / 2; i++) {
42
            if (s.charAt(left + i) != s.charAt(right - i)) {
43
                return false;
44
            }
45
        }
46
        return true;
47
    }
48
49
    public int findWord(String s, int left, int right) {
50
        return indices.getOrDefault(s.substring(left, right + 1), -1);
51
    }
52
}

复杂度分析：

  • 时间复杂度：$O(n \times m^2)$，其中$n$是字符串个数，$m$是字符串的平均长度。
  • 空间复杂度：$O(n \times m)$。