文章目录
前言
解题思路
边界
代码
前言
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1：
输入：words = [“abcd”,“dcba”,“lls”,“s”,“sssll”]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 [“dcbaabcd”,“abcddcba”,“slls”,“llssssll”]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
原始字符串放入hash表
找前缀
找后缀
所以前缀是回文的情况都试-遍，后缀是回文的情况都试一遍
边界
整体是回文的情况前后拼空字符串
自己的逆序
代码
class Solution {
public static List<List<Integer>> palindromePairs(String[] words) {
HashMap<String, Integer> wordset = new HashMap<>();
for (int i = 0; i < words.length; i++) {
wordset.put(words[i], i);
}
List<List<Integer>> res = new ArrayList<>();
//{ [6,23] 、 [7,13] }
for (int i = 0; i < words.length; i++) {
// i words[i]
// findAll(字符串，在i位置，wordset) 返回所有生成的结果返回
res.addAll(findAll(words[i], i, wordset));
}
return res;
}
public static List<List<Integer>> findAll(String word, int index, HashMap<String, Integer> words) {
List<List<Integer>> res = new ArrayList<>();
String reverse = reverse(word);
Integer rest = words.get("");
if (rest != null && rest != index && word.equals(reverse)) {
addRecord(res, rest, index);
addRecord(res, index, rest);
}
int[] rs = manacherss(word);
int mid = rs.length >> 1;
for (int i = 1; i < mid; i++) {
if (i - rs[i] == -1) {
rest = words.get(reverse.substring(0, mid - i));
if (rest != null && rest != index) {
addRecord(res, rest, index);
}
}
}
for (int i = mid + 1; i < rs.length; i++) {
if (i + rs[i] == rs.length) {
rest = words.get(reverse.substring((mid << 1) - i));
if (rest != null && rest != index) {
addRecord(res, index, rest);
}
}
}
return res;
}
public static void addRecord(List<List<Integer>> res, int left, int right) {
List<Integer> newr = new ArrayList<>();
newr.add(left);
newr.add(right);
res.add(newr);
}
public static int[] manacherss(String word) {
char[] mchs = manachercs(word);
int[] rs = new int[mchs.length];
int center = -1;
int pr = -1;
for (int i = 0; i != mchs.length; i++) {
rs[i] = pr > i ? Math.min(rs[(center << 1) - i], pr - i) : 1;
while (i + rs[i] < mchs.length && i - rs[i] > -1) {
if (mchs[i + rs[i]] != mchs[i - rs[i]]) {
break;
}
rs[i]++;
}
if (i + rs[i] > pr) {
pr = i + rs[i];
center = i;
}
}
return rs;
}
public static char[] manachercs(String word) {
char[] chs = word.toCharArray();
char[] mchs = new char[chs.length * 2 + 1];
int index = 0;
for (int i = 0; i != mchs.length; i++) {
mchs[i] = (i & 1) == 0 ? '#' : chs[index++];
}
return mchs;
}
public static String reverse(String str) {
char[] chs = str.toCharArray();
int l = 0;
int r = chs.length - 1;
while (l < r) {
char tmp = chs[l];
chs[l++] = chs[r];
chs[r--] = tmp;
}
return String.valueOf(chs);
}
}
