【数据结构和算法】确定两个字符串是否接近
其他系列文章导航
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.设置开…...
梦想与魔法:编程之路的挑战与荣耀
在年少轻狂的岁月里,我们都有过一些不切实际的梦想,渴望成为某种神奇的存在。我的梦想是成为一名神奇的码农,用键盘编织魔法,创造出炫酷的虚拟世界。然而,现实是残酷的,当我刚入门计算机领域时,…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...

解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...

MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...