当前位置：首页 > news >正文

两字符串拼接形成回文串

news 来源：原创 2024/5/10 20:03:16

leetcode336. 回文对

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

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

思路

选取一个字符串 $s$ ，将其分成两个部分 $l e f t$ , $r i g h t$ ，若存在一个字符串 $s^{'}$ 满足 $r i g h t$ 是回文串且 $s^{'}$ 的翻转等于 $l e f t$ ，那么 $s + s^{'}$ 是回文串。同样的若 $l e f t$ 是回文串且且 $s^{'}$ 的翻转等于 $r i g h t$ ，那么 $s^{'} + s$ 也是回文串。所以可以先预处理出来所有字符串的翻转字符串，那么判断 $l e f t$ 或 $r i g h t$ 是否存在 $s^{'}$ 是其翻转的时间复杂度为 $O (1)$ 。枚举 $l e f t$ 长度的时间复杂度为 $O (l)$ ，判断 $l e f t$ 或 $r i g h t$ 是否回文时间复杂度为 $O (l)$ 。所以总体的时间复杂度为 $O(nl^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;
    }
}