两字符串拼接形成回文串

leetcode336. 回文对

给定一组 互不相同 的单词， 找出所有 不同 的索引对$(i,j)$，使得列表中的两个单词， $words[i]+words[j]$ ，可拼接成回文串。
提示：

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] 由小写英文字母组成

思路

选取一个字符串$s$，将其分成两个部分$left$,$right$，若存在一个字符串$s^{\prime }$满足$right$是回文串且$s^{\prime }$的翻转等于$left$，那么$s+s^{\prime }$是回文串。同样的若$left$是回文串且且$s^{\prime }$的翻转等于$right$，那么$s^{\prime }+s$也是回文串。所以可以先预处理出来所有字符串的翻转字符串，那么判断$left$或$right$是否存在$s^{\prime }$是其翻转的时间复杂度为$O(1)$。枚举$left$长度的时间复杂度为$O(l)$，判断$left$或$right$是否回文时间复杂度为$O(l)$。所以总体的时间复杂度为$O(n{l}^2)$，其中$n$是字符串个数，$l$是字符串长度。数据有点弱，可以通过

代码

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        Map<String,Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            String s = words[i];
            String ss = new StringBuilder(s).reverse().toString();
            map.put(ss, i);
        }
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            String s = words[i];
            if(s.length() == 0) {
                continue;
            }
            for(int j = 0; j <= s.length(); j++) {
                String left = s.substring(0,j), right = s.substring(j);
                if(check(right) && map.get(left) != null && map.get(left) != i) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(i); tmp.add(map.get(left));
                    res.add(new ArrayList<>(tmp));
                }
                if(j != 0 && check(left) && map.get(right) != null && map.get(right) != i) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(map.get(right)); tmp.add(i); 
                    res.add(new ArrayList<>(tmp));
                }
            }
        }
        return res;
    }

    public boolean check(String s) {
        int l = 0, r = s.length() - 1;
        while(l < r) {
            if(s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++; r--;
        }
        return true;
    }
}
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