判断字符串是否接近:深入解析及优化【字符串、哈希表、优化过程】
本文将详细解析解决这个问题的思路,并逐步优化实现方案。
问题描述
给定两个字符串 word1 和 word2,如果通过以下操作可以将 word1 转换为 word2,则认为它们是接近的:
- 交换任意两个现有字符。
- 将一个现有字符的每次出现转换为另一个现有字符,并对另一个字符执行相同的操作。
你需要判断 word1 和 word2 是否接近。
示例
示例 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"
1657. 确定两个字符串是否接近 - 力扣(LeetCode)
解决思路
初步想法
最初的思路是通过使用 map 来记录字符及其出现的次数,然后通过 set 判断两个字符串的字符集是否一致,最后通过排序后的 vector 判断两个字符串的字符频次是否一致。
class Solution {
public:bool closeStrings(string word1, string word2) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);if(word1.size() != word2.size()) return false;// 首先判断map是不是都是一样的,包括char和int的个数;然后判断,是不是不管char,只要出现的次数一样就可以过unordered_map<char , int > m1 , m2;for(auto c : word1){m1[c] ++;}for(char d : word2){m2[d] ++;}if(m1 == m2) return true;unordered_set<char> s1(word1.begin() , word1.end());unordered_set<char> s2(word2.begin() , word2.end());if(s1 != s2) return false;vector<int> v1 , v2;for(auto pair : m1) v1.push_back(pair.second);for(auto pair : m2) v2.push_back(pair.second);sort(v1.begin() ,v1.end());sort(v2.begin() , v2.end());return v1 == v2;}
};
虽然初步思路可以解决问题,但在时间和空间复杂度上还有优化空间。
优化思路
1657. 确定两个字符串是否接近 - 力扣官方题解
官方解决方案利用了 word1 和 word2 仅包含小写字母这一条件,使用大小固定为 26 的 vector<int> 数组来记录字符频次。通过 ASCII 码减去 'a' 得到对应的下标,再进行操作。
class Solution {
public:bool closeStrings(string word1, string word2) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);vector<int> v1(26) , v2(26);for(auto c : word1){v1[c - 'a'] ++;}for(auto d : word2){v2[d - 'a'] ++;}for(int i = 0 ; i < 26 ; i ++){if(v1[i] == 0 && v2[i] > 0 || v1[i] > 0 && v2[i] == 0) return false;}sort(v1.begin() , v1.end());sort(v2.begin() , v2.end());return v1 == v2;}
};
详细解析
-
字符频次统计:
- 使用大小为 26 的
vector<int>数组count1和count2来记录word1和word2中每个字符的频次。通过c - 'a'得到对应的下标,这一步时间复杂度为O(n)。
- 使用大小为 26 的
-
字符集检查:
- 遍历
count1和count2,如果某个字符在一个字符串中出现而在另一个字符串中没有出现,则返回false。这一步的时间复杂度为O(1),因为数组大小固定为 26。
- 遍历
-
字符频次数组排序和比较:
- 对
count1和count2进行排序,然后比较两个排序后的数组是否相等。排序的时间复杂度为O(26 log 26),即O(1)。
- 对
为什么需要排序?
排序后的数组能直接比较每个字符的频次是否一致。这是因为交换字符不会改变频次,转换字符对频次排序也没有影响。通过排序并比较频次数组,我们能确保所有字符频次匹配。
复杂度分析
时间复杂度:
- 字符频次统计的时间复杂度为
O(n),其中n为字符串的长度。 - 字符集检查的时间复杂度为
O(1),因为count1和count2的大小固定为 26。 - 排序的时间复杂度为
O(26 log 26),即O(1)。
总的时间复杂度为 O(n)。
空间复杂度:
- 使用了两个大小为 26 的
vector<int>数组,空间复杂度为O(1)。
总结

通过优化,我们利用字符串仅包含小写字母这一特性,将问题简化为固定大小的数组操作,实现了更高效的解决方案。这种方法充分利用了题目中的限制条件,极大地优化了时间和空间复杂度。
相关文章:
判断字符串是否接近:深入解析及优化【字符串、哈希表、优化过程】
本文将详细解析解决这个问题的思路,并逐步优化实现方案。 问题描述 给定两个字符串 word1 和 word2,如果通过以下操作可以将 word1 转换为 word2,则认为它们是接近的: 交换任意两个现有字符。将一个现有字符的每次出现转换为另…...
C 和 C++ 中信号处理简单介绍
信号处理是编程中一个重要的主题,特别是在需要处理异步事件和错误情况的系统中。在 C 和 C 语言中,信号处理机制提供了一种优雅的方式来响应特定的系统事件,例如用户中断、异常情况或其他信号。在这里,我将详细介绍 C 和 C 中信号…...
什么是云边协同?
当今信息技术高速发展的时代,"云边协同"(Edge Cloud Collaboration)已经成为一个备受关注的话题。它涉及到云计算和边缘计算的结合,为数据处理、存储和应用提供了全新的可能性。本文将介绍云边协同的概念、优势以及在不…...
YOLOv5改进 | 主干网络 | 将backbone替换为MobileNetV2【小白必备教程+附完整代码】
秋招面试专栏推荐 :深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 💡💡💡本专栏所有程序均经过测试,可成功执行💡💡💡 专栏目录: 《YOLOv5入门 改…...
ARMxy边缘计算网关用于过程控制子系统
在现代工业生产中,过程控制系统的优化对于提高生产效率、保证产品质量、降低能源消耗等方面都具有重要意义。而 ARMxy 工控机作为一种高性能、高可靠性的工业控制设备,正逐渐成为过程控制系统优化的新选择。 ARMxy 工控机采用了先进的 ARM 架构处理器&am…...
Python | TypeError: unsupported operand type(s) for +=: ‘int’ and ‘str’
Python | TypeError: unsupported operand type(s) for : ‘int’ and ‘str’:深度解析 在Python编程中,遇到“TypeError: unsupported operand type(s) for : ‘int’ and ‘str’”这类错误通常意味着你尝试将一个整数(int)和…...
什么是开源什么是闭源?以及它们之间的关系
开源软件(Open Source Software) 定义:开源软件是指其源代码可以被公众访问和使用的软件。用户可以查看、修改和增强软件的源代码。 许可:通常遵循特定的开源许可证,如GNU通用公共许可证(GPL)、…...
SpringBoot+Mybatis Plus实际开发中的注解
SpringBoot+Mybatis Plus实际开发中的注解 实体类Service层Mapper层Controller层启动类配置类SpringBoot+Mybatis Plus实际开发中的注解 实体类 @Data : 底层实现了getter、setter、toString、hashCode、equals 和无参构造@AllArgsConstructor: 底层实现了有参构造@NoArgsCon…...
【香橙派系列教程】(八)一小时速通Python
【八】一小时速通Python 本章内容服务于香橙派下的开发,用C语言的视角来学习即可,会改就行。 详细说明,请看链接:python全篇教学 Python是一种动态解释型的编程语言,Python可以在Windows、UNIX、MAC等多种操作系统上 使用&…...
了解JavaScript 作用、历史和转变
JavaScript 是一种即时执行的脚本语言,其代码在浏览器环境中通过内置的 JavaScript 引擎被动态地一行接一行地解释执行。这一特性赋予了开发者极高的灵活性和效率,因为代码修改后能立即生效,无需经历编译过程,从而加速了开发周期和…...
遗传算法与深度学习实战——生命模拟与进化论
遗传算法与深度学习实战——生命模拟与进化论 0. 前言1. 模拟进化1.1 代码实现1.2 代码改进 2. 达尔文进化论3. 自然选择和适者生存3.1 适者生存3.2 进化计算中的生物学 小结系列链接 0. 前言 生命模拟通过计算机模拟生物体的基本特征、遗传机制、环境互动等,试图模…...
rt-thread H7 使用fdcan没有外接设备时或发送错误时线程被挂起的解决方案
一、问题查找 使用的开发版是硬石的H7芯片型号STM32H743IIT6,测试时发现如果外面没有连接CAN设备,程序调用CAN发送时会一直等待发送反馈,导致相关线程挂起。 在线仿真时发现是卡在can.c文件的168行_can_int_tx函数:rt_co…...
exptern “C“的作用,在 C 和 CPP 中分别调用 openblas 中的 gemm 为例
openblas提供的sgemm有两种方式,一种是通过cblas,另一种是直接声明并调用 sgemm_ 其中,cblas方式是更正规调用方法; 1,调用openblas的 sgemm 的两种方式 1.1 c语言程序中使用 sgemm hello_sgemm.c #include <st…...
如何提前预防网络威胁
一、引言 随着信息技术的迅猛进步,网络安全议题愈发凸显,成为社会各界不可忽视的重大挑战。近年来,一系列网络安全事件的爆发,如同惊雷般震撼着个人、企业及国家的安全防线,揭示了信息安全保护的紧迫性与复杂性。每一…...
ProviderRpc发送服务二将远程调用来的信息反序列化后调用服务方的方法,并将服务方的结果返回给发送方
在Provider的实现中,OnMessage函数中,处理接收到的连接RPC请求。将接收到的RPC请求(包含请求的对象,请求方法和 请求参数),接收到这些信息之后进行反序列化。得到这些参数之后我们即将要做的事情是去调用相…...
Io 35
FIleinputStream字节输入 package File.io;import java.io.*;public class io1 {public static void main(String[] args) throws IOException {// InputStream is new FileInputStream(new File("C:\\Users\\SUI\\Desktop\\Java1\\one\\src\\kaishi"));//简化Input…...
java基础概念11-方法
一、什么是方法 方法(method)是程序中最小的执行单元。 方法中的程序,要不然就是一起执行,要不然就是一起不执行!!! 二、方法的定义 在Java中,方法定义的一般格式如下:…...
大模型应用中的思维树(Tree of Thought)是什么?
大模型应用中的思维树(Tree of Thought)是什么? 大模型,特别是基于GPT(Generative Pre-trained Transformer)架构的模型,在处理复杂任务时,通常需要依赖某种形式的推理和决策机制。…...
学习记录(11):训练图片分类的算法
文章目录 一、卷积神经网络(CNN)架构1. ResNet(Residual Networks)2. DenseNet(Densely Connected Convolutional Networks)3. EfficientNet4. MobileNet 二、变换器(Transformer)架…...
上网防泄密,这些雷区不要碰!九招教你如何防泄密
李明:“最近看到不少关于信息泄露的新闻,真是让人担忧。咱们在工作中,稍有不慎就可能触碰到泄密的雷区啊。” 王芳:“确实,网络安全无小事。尤其是我们这种经常需要处理敏感信息的岗位,更得小心谨慎。那你…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
