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),是一种设计模式,用于根据不同的标准或条件从一组对象中筛选出符合条件的对象。它将筛选条件的逻辑封装在不同的过滤器…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...

算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...

DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...