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

LeetCode题练习与总结：回文对--336

news 2024/10/27 12:45:39

一、题目描述

给定一个由唯一字符串构成的 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 <= 5000
0 <= words[i].length <= 300
words[i] 由小写英文字母组成

二、解题思路

1. 创建一个HashMap，用于存储每个单词及其索引。

2. 遍历words数组，对于每个单词word，进行以下操作：

a. 将word反转，得到反转后的字符串rev。
b. 检查rev是否在HashMap中，如果在，并且rev的索引不等于当前单词的索引，则将当前单词的索引和rev的索引作为一个回文对添加到结果列表中，但需要注意确保word本身不是回文。
c. 对于每个单词word，将其拆分为前缀和后缀，分别检查前缀和后缀是否为回文。如果是，则在HashMap中查找相应的后缀和前缀，并添加到结果列表中，但需要注意确保后缀或前缀不为空字符串，除非另一个单词为空字符串。

3. 返回结果列表。

三、具体代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;class Solution {public List<List<Integer>> palindromePairs(String[] words) {List<List<Integer>> res = new ArrayList<>();HashMap<String, Integer> map = new HashMap<>();for (int i = 0; i < words.length; i++) {map.put(words[i], i);}for (int i = 0; i < words.length; i++) {String word = words[i];int len = word.length();for (int j = 0; j <= len; j++) {// 分割成前后缀String prefix = word.substring(0, j);String suffix = word.substring(j);// 如果前缀是回文，则查找反转后的后缀if (isPalindrome(prefix)) {String revSuffix = new StringBuilder(suffix).reverse().toString();if (map.containsKey(revSuffix) && map.get(revSuffix) != i && (suffix.length() == 0 || j != 0)) {res.add(Arrays.asList(map.get(revSuffix), i));}}// 如果后缀是回文，则查找反转后的前缀if (isPalindrome(suffix)) {String revPrefix = new StringBuilder(prefix).reverse().toString();if (map.containsKey(revPrefix) && map.get(revPrefix) != i) {res.add(Arrays.asList(i, map.get(revPrefix)));}}}}return res;}// 判断字符串是否为回文private boolean isPalindrome(String s) {int left = 0, right = s.length() - 1;while (left < right) {if (s.charAt(left++) != s.charAt(right--)) {return false;}}return true;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

创建HashMap存储单词及其索引：O(n * k)，其中n是单词数组的长度，k是单词的平均长度。这是因为每个单词都需要被插入到HashMap中。
遍历单词数组，对于每个单词word，我们再次遍历其所有可能的前缀和后缀：O(n * k^2)。这是因为对于每个单词，我们执行了k次操作（每次操作是分割单词并检查前缀或后缀是否为回文），每次操作需要O(k)时间（字符串分割和回文检查）。
在每次检查中，我们可能执行了字符串反转和HashMap查找操作：O(k)。

因此，总的时间复杂度是O(n * k^2)，因为这是最大的部分，它支配了总运行时间。

2. 空间复杂度

HashMap存储单词及其索引：O(n * k)，其中n是单词数组的长度，k是单词的平均长度。
结果列表res：在最坏情况下，如果每个单词都能与数组中的其他单词形成回文对，则结果列表的大小将是O(n^2)。
辅助空间，如字符串反转和临时字符串变量：O(k)。

因此，总的空间复杂度是O(n * k + n^2)，其中n * k是HashMap的空间，n^2是结果列表的空间。在大多数情况下，n^2可能是最大的部分，因此空间复杂度可以简化为O(n^2)。但是，如果单词长度远大于单词数量，那么HashMap的空间可能会成为主导因素，此时空间复杂度将是O(n * k)。

五、总结知识点

数据结构：
- ArrayList：用于存储结果列表，它是一个可调整大小的数组实现，提供了比标准数组更多的灵活性。
- HashMap：用于存储单词及其索引的映射，它提供了快速的查找功能。
字符串操作：
- substring：用于获取字符串的子串。
- StringBuilder：用于构建字符串，特别是进行字符串反转操作。
循环和条件语句：
- for循环：用于遍历数组或进行重复操作。
- if语句：用于条件判断。
算法逻辑：
- 回文检测：通过比较字符串的前后字符来检查一个字符串是否是回文。
- 字符串分割：将字符串分割成前缀和后缀，用于检查不同组合是否可以形成回文对。
函数定义和调用：
- private boolean isPalindrome(String s)：定义了一个私有辅助函数，用于检查字符串是否为回文。
- Arrays.asList(...)：用于创建并返回一个固定大小的列表。
错误处理和边界条件：
- 检查前缀或后缀是否为空字符串，以及是否与原字符串索引相同，以避免无效的回文对。