wordpress搭建学校网站,麻城网站制作公司,效果图怎么做出来的,桂林北站有核酸检测点吗一、题目描述
给定一个由唯一字符串构成的 0 索引 数组 words 。
回文对 是一对整数 (i, j) #xff0c;满足以下条件#xff1a;
0 i, j words.length#xff0c;i ! j #xff0c;并且words[i] words[j]#xff08;两个字符串的连接#xff09;是一个回文…一、题目描述
给定一个由唯一字符串构成的 0 索引 数组 words 。
回文对 是一对整数 (i, j) 满足以下条件
0 i, j words.lengthi ! 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] 由小写英文字母组成
二、解题思路
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 ListListInteger palindromePairs(String[] words) {ListListInteger res new ArrayList();HashMapString, 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(...)用于创建并返回一个固定大小的列表。 错误处理和边界条件 检查前缀或后缀是否为空字符串以及是否与原字符串索引相同以避免无效的回文对。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
