【数据结构和算法】确定两个字符串是否接近
其他系列文章导航
Java基础合集
数据结构与算法合集设计模式合集
多线程合集
分布式合集
ES合集
文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1操作 1 的本质:字符可以任意排列
2.2操作 2 的本质:出现次数是可以交换的
2.3算法思路
三、代码
四、总结
前言
这是力扣的1657题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。
一、题目描述
如果可以使用以下操作从一个字符串得到另一个字符串,则认为两个字符串 接近 :
- 操作 1:交换任意两个 现有 字符。
- 例如,
abcde -> aecdb
- 例如,
- 操作 2:将一个 现有 字符的每次出现转换为另一个 现有 字符,并对另一个字符执行相同的操作。
- 例如,
aacabb -> bbcbaa
(所有a
转化为b
,而所有的b
转换为a
)
- 例如,
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串,word1
和 word2
。如果 word1
和 word2
接近 ,就返回 true
;否则,返回 false
。
示例 1:
输入:word1 = "abc", word2 = "bca" 输出:true 解释:2 次操作从 word1 获得 word2 。 执行操作 1:"abc" -> "acb" 执行操作 1:"acb" -> "bca"示例 2:
输入:word1 = "a", word2 = "aa" 输出:false 解释:不管执行多少次操作,都无法从 word1 得到 word2 ,反之亦然。示例 3:
输入:word1 = "cabbba", word2 = "abbccc" 输出:true 解释:3 次操作从 word1 获得 word2 。 执行操作 1:"cabbba" -> "caabbb" 执行操作 2:"caabbb" -> "baaccc" 执行操作 2:"baaccc" -> "abbccc"示例 4:
输入:word1 = "cabbba", word2 = "aabbss" 输出:false 解释:不管执行多少次操作,都无法从 word1 得到 word2 ,反之亦然。
提示:
1 <= word1.length, word2.length <= 105
word1
和word2
仅包含小写英文字母
二、题解
本题的关键就是看清楚两个操作的本质!
2.1操作 1 的本质:字符可以任意排列
我们可以随意洗牌。
例如示例1的word1 = "abc", word2 = "bca" (把一叠扑克洗成另一叠扑克)。
如果字符一样,但对应的出现次数不一样呢?这就需要用到操作 2 了。
2.2操作 2 的本质:出现次数是可以交换的
以示例 3 为例。统计 s = cabbba 的字符出现次数:
- a 出现 2 次。
- b 出现 3 次。
- c 出现 1 次。
我们可以把 a 都变成 b,同时把 b 都变成 a。
这相当于交换 a 和 b 的出现次数,得到:
- a 出现 3 次。
- b 出现 2 次。
- c 出现 1 次。
然后交换 a 和 c 的出现次数,得到:
- a 出现 1 次。
- b 出现 2 次。
- c 出现 3 次。
这便是字符串 t = abbccc 的字符出现次数。
所以「出现次数」是可以任意排列的。
2.3算法思路
- 判断 word1 和 word2 的长度是否一样,如果不一样直接返回 false。
- 判断 word1 和 word2 的字符集合是否一样,如果不一样直接返回 false。例如 word1 中有字符 abc,word2 中有字符 zxc,我们无论如何都不能把 word1 变成 word2 。
- 判断 word1 的字符出现次数的集合,是否等于 word2 的字符出现次数的集合,等于返回 true,不等于返回 false。注意集合可以有相同元素,比如 aabbbccc 对应的集合就是 {2,3,3}。
三、代码
class Solution {public boolean closeStrings(String word1, String word2) {if (word1.length() != word2.length()) {//判断长度return false;}int[] count1 = new int[26], count2 = new int[26];for (char c : word1.toCharArray()) {count1[c - 97]++;}for (char c : word2.toCharArray()) {count2[c - 97]++;}for (int i = 0; i < 26; i++) {//判断字符是否相等if (count1[i] > 0 && count2[i] == 0 || count2[i] > 0 && count1[i] == 0) {return false;}}Arrays.sort(count1);Arrays.sort(count2);return Arrays.equals(count1, count2);//判断集合元素是否相等}
}
下面是简化版代码,但是上面的代码性能更好,如果两个字符串不相等,则直接不走下面的逻辑。
class Solution {public boolean closeStrings(String word1, String word2) {int[] count1 = new int[26], count2 = new int[26];for (char c : word1.toCharArray()) {count1[c - 97]++;}for (char c : word2.toCharArray()) {count2[c - 97]++;}for (int i = 0; i < 26; i++) {if (count1[i] > 0 && count2[i] == 0 || count2[i] > 0 && count1[i] == 0) {return false;}}Arrays.sort(count1);Arrays.sort(count2);return Arrays.equals(count1, count2);}
}
四、总结
复杂度分析:
- 时间复杂度:O(max{n1,n2}+ClogC),其中 n1 和 n2 分别是字符串 word1 和 word2 的长度,C=26 是字符集大小。
-
空间复杂度:O(C)。
相关文章:
【数据结构和算法】确定两个字符串是否接近
其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1操作 1 的本质:字符可以任意排列 2.2操作 2 的本质:出现次数是可以交换的 2.…...

[足式机器人]Part2 Dr. CAN学习笔记-Ch0-1矩阵的导数运算
本文仅供学习使用 本文参考: B站:DR_CAN Dr. CAN学习笔记-Ch0-1矩阵的导数运算 1. 标量向量方程对向量求导,分母布局,分子布局1.1 标量方程对向量的导数1.2 向量方程对向量的导数 2. 案例分析,线性回归3. 矩阵求导的链…...

如何让软文更具画面感,媒介盒子分享
写软文这种带有销售性质的文案时,总说要有画面感,要有想象空间。只有针对目标用户的感受的设计,要了解用户想的是什么,要用可视化的描述来影响用户的感受,今天媒介盒子就和大家分享:如何让软文更具画面感。…...

Hadoop学习笔记(HDP)-Part.19 安装Kafka
目录 Part.01 关于HDP Part.02 核心组件原理 Part.03 资源规划 Part.04 基础环境配置 Part.05 Yum源配置 Part.06 安装OracleJDK Part.07 安装MySQL Part.08 部署Ambari集群 Part.09 安装OpenLDAP Part.10 创建集群 Part.11 安装Kerberos Part.12 安装HDFS Part.13 安装Ranger …...

Arrays类练习 - Java
案例:自定义Book类,里面包含name和price,按price排序(从大到小)。要求使用两种方式排序,有一个 Book[] books 4本书对象。 使用前面学习过的传递实现Comparator接口匿名内部类,也称为定制排序。可以按照price (1)从大到…...

Java多线程:代码不只是在‘Hello World‘
Java线程好书推荐 概述01 多线程对于Java的意义02 为什么Java工程师必须掌握多线程03 Java多线程使用方式04 如何学好Java多线程写在末尾: 主页传送门:📀 传送 概述 摘要:互联网的每一个角落,无论是大型电商平台的秒杀…...

使用PCSS实现的实时阴影效果
PCSS的技术可以使得阴影呈现出近硬远软的效果,并且能够实时实现。 其核心理念是通过模拟光源的面积来产生更自然、更柔和的阴影边缘。 具体步骤: 1、生成shadowmap 2、在进行阴影的比较时候进行平均,并非之前的shadow map 或者之后完全的阴影…...

用于缓存一些固定名称的小组件
项目中,用于缓存姓名、地名、单位名称等一些较固定名称的id-name小组件。用于减少一些表的关连操作和冗余字段。优化代码结构。扩展也方便,写不同的枚举就行了。 具体用法: {NameCacheUser.USER.getName(userId);NameCacheUser.ACCOUNT.getN…...
Python 读取电子发票PDF 转成Excel
Python 读取电子发票PDF 转成Excel 目录 0.前提 1.python相关的处理PDF的库 2.实际好用的 3.实际代码 4.思考 0.前提 只识别普通电子发票PDF,提取其中某些关键内容到excel中。 1.python相关的处理PDF的库 如下4个库是经常更新维护的! pyP…...

我的项目问题
1.一点缩放和旋转就消失,需要再次平移才出现 解决方案:在显示当前图形时,显示已有图形。 2.每次点击平移,图形移动到上次点击的位置。 ho_RegionUnion.Dispose(); ho_RegionUnion ExpTmpOutVar_0;这两段代码放到显示之后的&am…...

【c】杨辉三角
下面介绍两种方法 1.利用上面性质的第五条,我们可以求各行各列的组合数 2.利用上面性质的第7条,我们可以用数组完成 下面附上代码 1. #include<stdio.h> void fact(int n ,int m )//求组合数 {long long int sum11;long long int sum21;int a…...
算法刷题之数组篇
题目一:两数之和 给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。 (注:返回的数组下标从1开始算起,保证target一定可以由数组里面2…...

TR转发路由器测评—云企业网实现跨地域跨VPC的网络互通测评实战【阿里云产品测评】
文章目录 一.转发路由器 Transit Router 测评1.1 准备阶段1.2 本文测评收获1.3 什么是云企业网实例、转发路由器实例和云数据传输服务 二.使用云企业网实现跨地域跨VPC的网络互通2.2 **测试连通性**2.3 网络拓扑如下: 心得:总结: 声明&#x…...

1.1美术理论基础
一、光影 物体呈现在人们眼前的时候,不同的受光面其明暗变化以及物体的影子。 1.什么是黑白灰 在美术中黑白灰指亮面、灰面、暗面,属于素描的三大面,主要体验一个物体的整体寿光过程。普遍存在于各种艺术和设计领域。黑白灰作品的出现&#x…...

【Java 基础】21 多线程同步与锁
文章目录 1.存在的问题2.使用同步解决问题1) synchronized2) volatile3) 锁 总结 用多线程过程中,有可能出现 多个线程同时处理(获取或修改等)同一个数据,这个时候就 会发生数据不同步的问题, 因此出现了同步和锁来…...

Python语言基础知识(一)
文章目录 1、Python内置对象介绍2、标识符与变量3、数据类型—数字4、数据类型—字符串与字节串5、数据类型—列表、元组、字典、集合6、运算符和表达式7、运算符和表达式—算术运算符8、运算符和表达式—关系运算符9.1、运算符和表达式— 成员测试运算符in9.2、运算符和表达式…...

Xilinx FPGA平台DDR3设计详解(三):DDR3 介绍
本文介绍一下常用的存储芯片DDR3,包括DDR3的芯片型号识别、DDR3芯片命名、DDR3的基本结构等知识,为后续掌握FPGA DDR3的读写控制打下坚实基础。 一、DDR3芯片型号 电路板上的镁光DDR3芯片上没有具体的型号名。 如果想知道具体的DDR3芯片型号&#…...
字典的遍历
字典不是有序的集合,就不能通过index来遍历了,那如何遍历字典呢? 方法一:直接用字典 for key in a_dict: print a_dict[key] 通过这样的结构可以的。 d {"liming" : 98, "wangli":95, "mali":90, "liping&q…...

Linux环境下的MySQL安装
文章目录 前提说明1.卸载内置环境2.检查系统安装包3.卸载这些默认安装包4.获取MySQL官方yum源5.安装MySQLyum源,对比前后yum源6.查看yum源是否生效7.安装MySQL服务8.查看相对应的配置文件9.启动服务10.查看启动服务11.登录方法一12.登录方法二13.登录方法三14.设置开…...
梦想与魔法:编程之路的挑战与荣耀
在年少轻狂的岁月里,我们都有过一些不切实际的梦想,渴望成为某种神奇的存在。我的梦想是成为一名神奇的码农,用键盘编织魔法,创造出炫酷的虚拟世界。然而,现实是残酷的,当我刚入门计算机领域时,…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...