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(...)
:用于创建并返回一个固定大小的列表。
-
错误处理和边界条件:
- 检查前缀或后缀是否为空字符串,以及是否与原字符串索引相同,以避免无效的回文对。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
相关文章:
LeetCode题练习与总结:回文对--336
一、题目描述 给定一个由唯一字符串构成的 0 索引 数组 words 。 回文对 是一对整数 (i, j) ,满足以下条件: 0 < i, j < words.length,i ! j ,并且words[i] words[j](两个字符串的连接)是一个回文…...
CesiumJS 案例 P7:添加指定长宽的图片图层(原点分别为图片图层的中心点、左上角顶点、右上角顶点、左下角顶点、右下角顶点)
CesiumJS CesiumJS API:https://cesium.com/learn/cesiumjs/ref-doc/index.html CesiumJS 是一个开源的 JavaScript 库,它用于在网页中创建和控制 3D 地球仪(地图) 一、添加指定长宽的图片图层(原点为图片图层的中心…...
Redis 主从同步 问题
前言 相关系列 《Redis & 目录》(持续更新)《Redis & 主从同步 & 源码》(学习过程/多有漏误/仅作参考/不再更新)《Redis & 主从同步 & 总结》(学习总结/最新最准/持续更新)《Redis &a…...
【SQL Server】探讨 IN 和 EXISTS之间的区别
前言 在使用 SQL 查询相关表数据时,通常需要根据另一个表中的值来筛选数据。而 IN 与 EXISTS 子句都是用于此场景的常用方式,但使用时两者存在工作方式不同。它们使用上的选择会显著影响查询的性能,尤其是在大型数据集中。本文我们一起探讨 IN 和 EXISTS 之间的区别、使用与…...
清理pip和conda缓存
当用户目录没有空间时,可清理pip和conda缓存 清理conda缓存: conda clean --all清理pip缓存: pip cache purgeNote: 可以利用软链接,将用户目录下的文件链接到其他位置 首先移动文件或文件夹到其他位置 mv ~/test /…...
git rebase和merge的区别
Git merge和Git rebase是两种不同的合并策略,它们在处理分支合并时有各自的优点和缺点。 Git fetch git fetch 命令用于从远程仓库获取最新的更改,但不会自动合并这些更改到你的本地分支。它会下载远程仓库的所有分支和标签,并更新你的本地…...

【elkb】linux麒麟v10安装ELKB 8.8.X版本(ARM架构)
下载软件 相关版本信息 elasticsearch:8.8.1kibana:8.8.1logstash:8.8.1filebeat:8.8.1 下载地址 https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-8.8.1-linux-aarch64.tar.gzhttps://artifacts.elastic…...
bluez hid host介绍,连接键盘/鼠标/手柄不是梦,安排
零. 前言 由于Bluez的介绍文档有限,以及对Linux 系统/驱动概念、D-Bus 通信和蓝牙协议都有要求,加上网络上其实没有一个完整的介绍Bluez系列的文档,所以不管是蓝牙初学者还是蓝牙从业人员,都有不小的难度,学习曲线也相对较陡,所以我有了这个想法,专门对Bluez做一个系统…...
GPT打数模——电商品类货量预测及品类分仓规划
背景 电商企业在各区域的商品存储主要由多个仓库组成的仓群承担。其中存储的商品主要按照属性(品类、件型等)进行划分和打标,便于进行库存管理。图 1 是一个简化的示意图,商品品类各异,件数众多,必须将这些…...

华为OD机试 - 螺旋数字矩阵 - 矩阵(Python/JS/C/C++ 2024 D卷 100分)
华为OD机试 2024E卷题库疯狂收录中,刷题点这里 专栏导读 本专栏收录于《华为OD机试真题(Python/JS/C/C)》。 刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,…...

分类预测 | GCN图卷积神经网络多特征分类预测(MATLAB)
分类预测 | GCN图卷积神经网络多特征分类预测(MATLAB) 目录 分类预测 | GCN图卷积神经网络多特征分类预测(MATLAB)分类效果基本介绍程序设计参考资料分类效果 基本介绍 GCN图卷积神经网络多特征分类预测(MATLAB) 在图卷积神经网络(GCN)中,多特征分类...

FPGA搭建PCIE3.0通信架构简单读写测试,基于XDMA中断模式,提供3套工程源码和技术支持
目录 1、前言工程概述免责声明 2、相关方案推荐我已有的PCIE方案本博客方案的PCIE2.0版本 3、PCIE基础知识4、工程详细设计方案工程设计原理框图XDMA配置及使用XDMA中断模块数据缓存架构用户逻辑Windows版本XDMA驱动安装Linux版本XDMA驱动安装测试应用程序工程源码架构PCIE上板…...

App相关技术以及打包
平时小伙伴们自己的博客网站只能在浏览器打开,但是有时候你想要制作自己独立个人博客app,宣传并推广自己的app,打造个人ip。如何把自己的web博客网站打包成安卓app? 1.开发App的相关技术使⽤ ⽬前市⾯上的移动互联开发技术主要分…...

【unity】【游戏开发】Unity代码不给提示怎么办?
【现象】 Unity用着用着忽然VS脚本不给提示了。 【分析】 重启Unity无效 重启VS无效 重装VS无效 感觉应该是项目设置问题 【最终方法】 打开Edit->Preferences。 如果是这个画面就把Script Editor改成自己的VS编辑器。 变成下面这个样子,点击Regenerate Pr…...
Kubernetes固定Pod IP和Mac地址
方案1: 在 Calico GitHub Issues#5196 问题的 commits#6249 提交中,引入新的 Pod 注释cni.projectcalico.org/hwAddr,用于将指定的 MAC 地址分配给容器端 Veth 接口。 将Calico升级至v3.24.1或以上版本,使用如下注解轻松设置Pod…...
计算机组成原理之数据的对齐和大/小端存放方式、计算机中数据对齐的具体方式有哪些
1、计算机组成原理之数据的对齐和大/小端存放方式 数据对齐 数据对齐是处理器为了提高处理性能而对存取数据的起始地址所提出的一种要求。 系统一次性读取内存中数据的大小是固定的,例如字长为32位的操作系统,默认的一次读取4字节内容。因此ÿ…...

【学术论文投稿】Windows11开发指南:打造卓越应用的必备攻略
【IEEE出版南方科技大学】第十一届电气工程与自动化国际会议(IFEEA 2024)_艾思科蓝_学术一站式服务平台 更多学术会议论文投稿请看:https://ais.cn/u/nuyAF3 目录 引言 一、Windows11开发环境搭建 二、Windows11关键新特性 三、Windows11设计指南 …...

【毕业论文+源码】基于SSM(Spring + Spring MVC + MyBatis)的房屋租赁系统
创建一个基于SSM(Spring Spring MVC MyBatis)框架的房屋租赁系统是一个涉及多个步骤的过程。这个过程包括但不限于需求分析、数据库设计、前端界面设计以及后端逻辑实现等。 1. 需求分析 首先,明确你的房屋租赁系统的功能需求。例如&…...
【golang】解析 JSON到指定结构体
1.解析[1,2,3,4]数组类型的json package mainimport ("encoding/json""fmt" )func main() {// JSON 数据jsonData : [1, 2, 3, 4]// 定义一个切片来接收解析后的数据var numbers []int// 解析 JSON 数据到切片err : json.Unmarshal([]byte(jsonData), &am…...
设计模式——过滤器模式
一、定义和概念 定义 C 过滤器模式(Filter Pattern)也称为标准模式(Criteria Pattern),是一种设计模式,用于根据不同的标准或条件从一组对象中筛选出符合条件的对象。它将筛选条件的逻辑封装在不同的过滤器…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...

Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...