判断字符串是否接近:深入解析及优化【字符串、哈希表、优化过程】
本文将详细解析解决这个问题的思路,并逐步优化实现方案。
问题描述
给定两个字符串 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)架…...
上网防泄密,这些雷区不要碰!九招教你如何防泄密
李明:“最近看到不少关于信息泄露的新闻,真是让人担忧。咱们在工作中,稍有不慎就可能触碰到泄密的雷区啊。” 王芳:“确实,网络安全无小事。尤其是我们这种经常需要处理敏感信息的岗位,更得小心谨慎。那你…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
