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

一、题目描述

给定一个由唯一字符串构成的 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(...)：用于创建并返回一个固定大小的列表。

• 错误处理和边界条件：

  • 检查前缀或后缀是否为空字符串，以及是否与原字符串索引相同，以避免无效的回文对。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。