回文对
难度:
标签:
题目描述
给定一个由唯一字符串构成的 0 索引 数组 words 。
回文对 是一对整数 (i, j) ，满足以下条件：
0 <= i, j < words.length，i != j，并且words[i] + words[j]（两个字符串的连接）是一个回文串。
返回一个数组，它包含 words 中所有满足 回文对 条件的字符串。
你必须设计一个时间复杂度为 O(sum of words[i].length) 的算法。
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
示例 3：
输入：words = ["a",""] 输出：[[0,1],[1,0]]
提示：
1 <= words.length <= 50000 <= words[i].length <= 300words[i]由小写英文字母组成
代码结果
运行时间: 891 ms, 内存: 26.5 MB
/*
* 思路：
* 1. 使用 Java Stream 和 Map 结合实现查找回文对。
* 2. 使用哈希表存储每个单词及其索引。
* 3. 通过 Stream 对每个单词进行处理，生成可能的回文对。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class PalindromePairsStream {
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> wordMap = IntStream.range(0, words.length)
.boxed()
.collect(Collectors.toMap(i -> words[i], i -> i));
return IntStream.range(0, words.length)
.boxed()
.flatMap(i -> IntStream.range(0, words[i].length() + 1)
.boxed()
.flatMap(j -> {
List<List<Integer>> pairs = new ArrayList<>();
String prefix = words[i].substring(0, j);
String suffix = words[i].substring(j);
if (isPalindrome(prefix)) {
String reversedSuffix = new StringBuilder(suffix).reverse().toString();
if (wordMap.containsKey(reversedSuffix) && wordMap.get(reversedSuffix) != i) {
pairs.add(List.of(wordMap.get(reversedSuffix), i));
}
}
if (isPalindrome(suffix) && suffix.length() != 0) {
String reversedPrefix = new StringBuilder(prefix).reverse().toString();
if (wordMap.containsKey(reversedPrefix) && wordMap.get(reversedPrefix) != i) {
pairs.add(List.of(i, wordMap.get(reversedPrefix)));
}
}
return pairs.stream();
}))
.collect(Collectors.toList());
}
private boolean isPalindrome(String str) {
int left = 0, right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
解释
方法:
这个题解使用了字典 backward 来存储单词的逆序作为键，原单词的索引作为值。然后遍历每个单词，判断以下情况：
1. 如果当前单词的逆序在字典中，且不是当前单词自身，则可以组成回文对。
2. 如果当前单词是回文串，且空串在字典中，则可以组成两个回文对。
3. 将当前单词划分为左右两部分，如果左边部分的逆序在字典中，且右边部分是回文串，则可以组成回文对。
4. 将当前单词划分为左右两部分，如果右边部分的逆序在字典中，且左边部分是回文串，则可以组成回文对。
最后返回所有找到的回文对。
时间复杂度:
O(n*k)，其中 n 为单词数组的长度，k 为单词的平均长度。
空间复杂度:
O(n^2)，其中 n 为单词数组的长度。
代码细节讲解
🦆
在题解的情况2中，为什么提到'当前单词是回文串，且空串在字典中，则可以组成两个回文对'？空串应该如何处理才能确保算法的正确性和效率？
▷🦆
对于情况3和情况4，题解说明了将单词划分为两部分，但是如何确保这种划分和逆序的查找能够有效发现所有可能的回文对？
▷🦆
题解中的算法实现似乎没有显式地处理单词数组中存在重复单词的情况，给定题目条件是唯一字符串，但如果条件改变，该如何调整算法以处理重复字符串？
▷🦆
题解提到的情况2中，如果空字符串不在字典中，但是存在一个是回文串的单词，这种情况下的处理逻辑是什么？
▷