LeetCode 249 解法揭秘:如何把“abc”和“bcd”分到一组?
文章目录
- 摘要
- 描述
- 痛点分析 & 实际应用场景
- Swift 题解答案
- 可运行 Demo 代码
- 题解代码分析
- 差值是怎么来的?
- 为什么加 `+26` 再 `%26`?
- 示例测试及结果
- 时间复杂度分析
- 空间复杂度分析
- 总结
摘要
你有没有遇到过这种情况:有一堆字符串,看起来只是“平移”了一下,比如 abc
-> bcd
,或者 az
-> ba
,虽然字母换了,但它们给人的感觉还是很像。LeetCode 第 249 题就正好考了这个点:把所有属于同一个“移位字符串序列”的东西分成一组。
别看题目挺简单,其实要把这类“差不多但不完全一样”的字符串精准归类,还是有点技术含量的。这篇文章用 Swift 来做这道题,并结合实际开发场景讲讲它能怎么用,还会附上完整可运行的 Demo 和讲解。
描述
我们有一个只包含小写字母的字符串列表,比如:
["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
我们希望把其中属于同一“移位序列”的字符串分组。比如:
"abc"
->"bcd"
->"cde"
,这类的归一组"az"
和"ba"
,虽然乍看没啥关系,但实际上也算同一个“偏移规律”,可以放一起"acef"
没有能跟它组队的,就自己一组
最后的输出应该是这样:
[["abc","bcd","xyz"],["az","ba"],["acef"],["a","z"]
]
痛点分析 & 实际应用场景
这个题其实挺有意思,因为它背后解决的是一种非常实际的问题:怎么找出那些“表面不一样、但本质上变化规律相同”的东西。你可能会觉得这玩意平时开发用不着,但我们来看几个真实场景:
1. 防刷系统识别:
在社交平台上,有些用户发骚扰信息时会稍微改一下内容,比如:
"hi there" -> "ij uifsf" -> "jk vjgtg"
其实就是每个字母往后挪了一位、两位、三位…你肉眼一看很像,但程序该怎么识别出来这是一类“伪装”的垃圾信息呢?这道题的逻辑就能用上。
2. 智能输入法候选词推荐:
用户打了个错别字,比如输入 bcd
,其实是想输入 abc
,那我们能不能把这种偏移关系也识别出来作为候选词推荐?靠的也是类似的偏移计算。
3. 密码安全检测:
用户试图设置一个和之前密码差不多的新密码,比如原来是 abc123
,新设置成 bcd123
,其实没啥变化。这种逻辑在安全校验里也是经常遇到的。
4. 自然语言处理中的文本聚类:
比如说一个聊天机器人收集到很多用户的意图,但有一类人喜欢换着字母输入(变形词),你就需要判断这是不是同一类话术模式。
说到底,这题就是在考“如何识别相似但又不是完全一样的内容”。
Swift 题解答案
思路其实不复杂,我们可以对每个字符串生成一个“差值序列”当作 key,比如:
abc
的字符间差值是 [1, 1]bcd
也是 [1, 1]az
是 [25]
我们把这些差值转换成字符串作为 map 的 key,然后分组就行了。
可运行 Demo 代码
import Foundationfunc groupStrings(_ strings: [String]) -> [[String]] {var groups = [String: [String]]()for str in strings {var key = ""let chars = Array(str)for i in 1..<chars.count {let diff = (Int(chars[i].asciiValue!) - Int(chars[i - 1].asciiValue!) + 26) % 26key += "\(diff),"}groups[key, default: []].append(str)}return Array(groups.values)
}
题解代码分析
我们来拆解一下关键部分:
差值是怎么来的?
举个例子,abc
中:
'b' - 'a' = 1
'c' - 'b' = 1
差值数组就是 [1, 1]
,我们转成 "1,1,"
当作 key。只要差值序列一样,说明这个字符串和前面的某个是“移位版本”。
为什么加 +26
再 %26
?
因为我们要处理 'z' -> 'a'
这种环绕关系。比如:
let diff = ('a' - 'z' + 26) % 26 // 结果是 1
这样 az
和 ba
这类看似不连贯的字符串,也能算是同一组。
示例测试及结果
来跑个例子看看效果:
let input = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
let result = groupStrings(input)for group in result {print(group)
}
打印结果:
["abc", "bcd", "xyz"]
["az", "ba"]
["acef"]
["a", "z"]
这就和题目期望一模一样。
时间复杂度分析
假设我们有 n
个字符串,每个字符串长度最多 k
:
- 外层遍历所有字符串是
O(n)
- 内层处理每个字符串生成 key 是
O(k)
所以总体复杂度是 O(n * k)
空间复杂度分析
我们用了一个字典来分组,最坏情况下每个字符串都分一组,字典大小也是 O(n * k)
(因为 key 是字符串差值序列)
总结
这题核心是找出规律:“移位”的本质就是字符间的差值一致。不需要真的去“移”字符串,只要你能拿到这个差值序列,你就能判断两个字符串是不是一个套路。
另外也提醒我们,在实际开发中处理字符串聚类或异常识别时,找对特征比暴力匹配要高效得多。这个题的差值 key 就是一个很实用的“特征”。
如果你在做一些输入推荐、内容防刷、文本归类功能,不妨试试看用类似的方式去做聚类、查重或识别。
相关文章:
LeetCode 249 解法揭秘:如何把“abc”和“bcd”分到一组?
文章目录 摘要描述痛点分析 & 实际应用场景Swift 题解答案可运行 Demo 代码题解代码分析差值是怎么来的?为什么加 26 再 %26? 示例测试及结果时间复杂度分析空间复杂度分析总结 摘要 你有没有遇到过这种情况:有一堆字符串,看…...
【Kafka基础】topic命令行工具kafka-topics.sh:基础操作命令解析
Kafka作为分布式流处理平台的核心组件,其主题管理是每个开发者必须掌握的关键技能。本文将详细解析kafka-topics.sh工具的使用技巧,从基础操作操作开始,助您轻松驾驭Kafka主题管理。 1 创建主题 /export/home/kafka_zk/kafka_2.13-2.7.1/bin/…...
C++ 排序(1)
以下是一些插入排序的代码 1.插入排序 1.直接插入排序 // 升序 // 最坏:O(N^2) 逆序 // 最好:O(N) 顺序有序 void InsertSort(vector<int>& a, int n) {for (int i 1; i < n; i){int end i - 1;int tmp a[i];// 将tmp插入到[0,en…...
Business English Certificates (BEC) 高频词汇学习
Business English Certificates {BEC} 高频词汇 References Cambridge English: Business Certificates, also known as Business English Certificates (BEC), are a suite of three English language qualifications for international business. abandon /əˈbndən/ vt. …...
信息系统项目管理中各个知识领域的概要描述及其管理流程
1. 立项管理 涵义:评估项目可行性,决定是否启动。 流程: 需求分析:识别业务需求或问题。 可行性研究:技术、经济、法律等可行性分析。 项目建议书:提交初步方案。 立项评审:高层审批。 项目…...
OpenAI推出PaperBench
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
基于LSTM的文本分类2——文本数据处理
前言 由于计算机无法认识到文字内容,因此在训练模型时需要将文字映射到计算机能够识别的编码内容。 映射的流程如下: 首先将文字内容按照词表映射到成唯一的数字ID。比如“我爱中国”,将“中”映射为1,将“国”映射到2。再将文…...
神经网络与深度学习:案例与实践——第三章(2)
神经网络与深度学习:案例与实践——第三章(2) 基于Softmax回归的多分类任务 Logistic回归可以有效地解决二分类问题,但在分类任务中,还有一类多分类问题,即类别数 C大于2 的分类问题。Softmax回归就是Log…...
Maven/Gradle的讲解
一、为什么需要构建工具? 在理解 Maven/Gradle 之前,先明确它们解决的问题: 依赖管理:项目中可能需要引入第三方库(如 Spring、JUnit 等),手动下载和管理这些库的版本非常麻烦。标…...
常见的HR面问题汇总
⚠️注意:以下仅是个人对问题的参考,具体情况视个人情况而定~ 1. 你觉得你有哪些优点和缺点? 优点:学习能力强,遇到问题会主动思考和查找解决方案;有责任心,对待工作认真负责&#…...
把握数据治理关键,释放企业数据潜能
数据治理是对数据资产管理行使权力和控制的活动集合,以下是关于它的详细介绍: 一、定义 数据治理是指从使用零散数据变为使用统一主数据、从具有很少或没有组织和流程治理到企业范围内的综合数据治理、从尝试处理主数据混乱状况到主数据井井有条的一个…...
优化 Web 性能:处理非合成动画(Non-Composited Animations)
在 Web 开发中,动画能够增强用户体验,但低效的动画实现可能导致性能问题。Google 的 Lighthouse 工具在性能审计中特别关注“非合成动画”(Non-Composited Animations),指出这些动画可能增加主线程负担,影响…...
房地产之后:探寻可持续扩张的产业与 GDP 新思
在经济发展的长河中,房地产长期占据着支柱产业的重要地位。其之所以能担当此重任,根源在于它深度嵌入了人们的生活与经济体系。住房,作为人类最基本的需求之一,具有不可替代的刚性。与其他现买按需生产的产业不同,房地产有着独特的消费逻辑。人们为了拥有一个稳定的居住之…...
Chapter02_数字图像处理基础
文章目录 图像的表示⭐模拟图像→数字图像均匀采样和量化均匀采样均匀量化 非均匀采样和量化 数字图像的表示二值图像灰度图像彩色图像 ⭐空间分辨率和灰度分辨率空间分辨率灰度分辨率 ⭐图像视觉效果影响因素采样数变化对图像视觉效果的影响空间分辨率变化对图像视觉效果的影响…...
【Android】UI开发:XML布局与Jetpack Compose的全面对比指南
随着Google推出Jetpack Compose这一现代化工具,我们面临一个关键选择:继续使用传统的XML布局,还是转向Compose? 一、语法对比:两种不同的构建方式 1. XML布局:基于标签的静态结构 XML通过嵌套标签定义UI元…...
浙大:LLM具身推理引擎Embodied-Reasoner
📖标题:Embodied-Reasoner: Synergizing Visual Search, Reasoning, and Action for Embodied Interactive Tasks 🌐来源:arXiv, 2503.21696 🌟摘要 🔸深度思维模型的最新进展已经证明了数学和编码任务的…...
form+ffmpeg+opus录音压缩音频
说明: formffmpegopus录音压缩音频 效果图: step1:opus格式录音 C:\Users\wangrusheng\RiderProjects\WinFormsApp11\WinFormsApp11\Form1.cs using System; using System.Diagnostics; using System.IO; using System.Windows.Forms;namespace WinFo…...
win10 笔记本电脑安装 pytorch+cuda+gpu 大模型开发环境过程记录
win10 笔记本电脑安装 pytorchcudagpu 大模型开发环境过程记录 文章部分内容参考 deepseek。 以下使用命令行工具 mingw64。 安装 Anaconda 安装位置: /c/DEVPACK/Anaconda3 然后安装 Python 3.10.16 (略) $ conda create -n pytorch_…...
LeetCode 2442:统计反转后的不同整数数量
目录 核心思想:数字的“拆分”与“重组” 分步拆解(以输入 123 为例) 关键操作详解 为什么能处理中间或末尾的0? 数学本质 总结 题目描述 解题思路 代码实现 代码解析 复杂度分析 示例演示 总结 核心思想:…...
获取inode的完整路径包含挂载的路径
一、背景 在之前的博客 缺页异常导致的iowait打印出相关文件的绝对路径-CSDN博客 里的 2.2.3 一节和 关于inode,dentry结合软链接及硬链接的实验-CSDN博客 里,我们讲到了在内核里通过inode获取inode对应的绝对路径的方法。对于根目录下的文件而言&#…...
解决上传PDF、视频、音频等格式文件到FTP站点时报错“将文件复制到FTP服务器时发生错误。请检查是否有权限将文件放到该服务器上”问题
一、问题描述 可以将文本文件(.txt格式),图像文件(.jpg、.png等格式)上传到我们的FTP服务器上;但是上传一些PDF文件、视频等文件时就会报错“ 将文件复制到FTP服务器时发生错误。请检查是否有权限将文件放到该服务器上。 详细信息: 200 Type set to l. 227 Entering Pas…...
git push
在 git push 命令中,分支名称的顺序和含义非常重要。其基本格式如下: git push <remote> <local_branch>:<remote_branch>各部分解释 <remote>:远程仓库的名称(如 origin)。<local_branc…...
Java中的四大引用类型详解
Java中的四大引用类型详解:强引用、软引用、弱引用、虚引用 1. 引用类型概览 Java提供了四种不同强度的引用类型,用于控制对象的生命周期和垃圾回收行为: 引用类型回收时机典型应用场景是否影响GC强引用永不回收(除非断开引用&…...
MySQL慢查询日志通俗指南
🍀 前言 如果你发现自己新写或者重写的接口查询速度变慢,你怎么定位原因呢?可以用explain分析我们的SQL原生代码,又或者可以考虑使用MySQL慢查询日志。这篇文章主要讲述什么是慢查询日志以及开发中可能用到的场景。 但是&#x…...
Kafka 如何保证消息可靠性?
Kafka 保证消息可靠性主要通过以下几个机制来实现,从生产者到消费者的整个链路上都设计了相应的保障措施: 1. 生产者(Producer)端的可靠性 ✅ a. acks 参数(确认机制) acks0:生产者不等待任何…...
【嵌入式系统设计师】知识点:第2章 嵌入式系统硬件基础知识
提示:“软考通关秘籍” 专栏围绕软考展开,全面涵盖了如嵌入式系统设计师、数据库系统工程师、信息系统管理工程师等多个软考方向的知识点。从计算机体系结构、存储系统等基础知识,到程序语言概述、算法、数据库技术(包括关系数据库、非关系型数据库、SQL 语言、数据仓库等)…...
C++重载运算符的本质
C 中运算符重载的本质就是函数调用,编译器会将运算符表达式转换为对特定函数的直接调用。以下是具体原理和实现细节: 1. 运算符重载的底层实现 当重载一个运算符(如 、、<<)时,实际上是在定义一个特殊名称的函数…...
Python解决“数字插入”问题
Python解决“数字插入”问题 问题描述测试样例解题思路代码 问题描述 小U手中有两个数字 a 和 b。第一个数字是一个任意的正整数,而第二个数字是一个非负整数。她的任务是将第二个数字 b 插入到第一个数字 a 的某个位置,以形成一个最大的可能数字。 你…...
深入讲解:智能合约中的读写方法
前言 在探秘区块链开发:智能合约在 DApp 中的地位及与传统开发差异一文中我提到对于智能合约中所有的写入其实都算是交易。而在一个完整的智能合约代码中最大的两个组成部分就是读取和写入。 本文将为你深入探讨该两者方法之间的区别。 写方法 写方法其实就是对区块链这一…...
Java进阶之旅-day05:网络编程
引言 在当今数字化的时代,网络编程在软件开发中扮演着至关重要的角色。Java 作为一门广泛应用的编程语言,提供了强大的网络编程能力。今天,我们深入学习了 Java 网络编程的基础知识,包括基本的通信架构、网络编程三要素、IP 地址、…...
Eliet Chat开发日志:信令服务器注册与通信过程
目录 1. 架构设计:信令服务器与客户端 2. 选择技术栈 3. 实现信令服务器 4. 客户端实现 5. 测试 6. 下一步计划 日期:2025年4月5日 今天的工作重点是实现两个设备通过信令服务器注册并请求对方公网地址信息,以便能够进行点对点通信。我…...
如何设计一个本地缓存
想获取更多高质量的Java技术文章?欢迎访问Java技术小馆官网,持续更新优质内容,助力技术成长 Java技术小馆官网https://www.yuque.com/jtostring 如何设计一个本地缓存 随着系统的复杂性和数据量的增加,如何快速响应用户请求、减…...
2024版idea使用Lombok时报找不到符号
今天在springboot项目中使用Lombok的Builder注解,启动时居然报了找不到符号的错,如下图 于是开始了漫长的寻找之路,首先去settings->Plugins中看自己的Lombok插件是否启动,发现确实是如此,然后看网上的教程去加上这…...
[Android安卓移动计算]:新建项目和配置环境步骤
文章目录 一:AndroidStudio 创建项目1. New Project2. 选择:Empty Activity 二:配置和下载SDK点击SDK 配置按钮选择API32和Android 9.0(Pie)再点击Apply点击接受条款声明进行安装 安装完后点击NEXT和OK出现:…...
$R^n$平面约束下的向量列
原向量: x → \overset{\rightarrow}{x} x→ 与 x → \overset{\rightarrow}{x} x→法向相同的法向量(与 x → \overset{\rightarrow}{x} x→同向) ( x → ⋅ n → ∣ n → ∣ 2 ) n → (\frac{\overset{\rightarrow}x\cdot\overset{\righta…...
混合编程的架构
在混合使用QML和Qt Widgets的环境中,是否必须严格遵循分层架构需要根据项目规模和复杂度来决定。以下是具体的决策指南和实施建议: 一、分层架构的适用性分析 #mermaid-svg-61Mlp9MrpFOoZPAO {font-family:"trebuchet ms",verdana,arial,sans…...
联网汽车陷入网络安全危机
有人能够入侵并控制汽车这一事实本身就令人恐惧,电影中的场景变成了现实。再加上汽车中的软件会处理和存储我们的个人数据,这种恐惧达到了一个新的高度。 一旦发生安全漏洞,我们的驾驶数据、联系人、通话记录、消息甚至位置信息等信息都可能…...
基于Spark的招聘数据预测分析推荐系统
【Spark】基于Spark的招聘数据预测分析推荐系统 (完整系统源码开发笔记详细部署教程)✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统能够高效处理海量招聘数据,利用Spark的强大计算能力实现快速分析和预测。该系…...
基于Spark的酒店数据分析系统
【Spark】基于Spark的酒店数据分析系统 (完整系统源码开发笔记详细部署教程)✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 本项目基于Python语言开发,借助Django进行后台框架的开发,搭建大数据虚拟机集群…...
网络安全L2TP实验
在FW1上,将接口g1/0/0添加进去trust区域 [USG6000V1]firewall zone trust [USG6000V1-zone-trust]add interface GigabitEthernet 1/0/0 在放通安全策略 在FW2上配置ip [USG6000V1]int g1/0/1 [USG6000V1-GigabitEthernet1/0/1]ip address 20.1.1.1 24 [USG6000…...
18.1.go连接redis
开发调试 Tiny RDM:跨平台GUI工具windows版本下载 https://download.csdn.net/download/chxii/90562932 支持多种格式查看:内置高级文本代码编辑器,支持语法高亮/代码折叠/错误提示 便捷搜索过滤:使用正则匹配搜索键后,仍可进行二级过滤,组合筛选数据更方便 调试分析…...
innodb如何实现mvcc的
InnoDB 实现 MVCC(多版本并发控制)的机制主要依赖于 Undo Log(回滚日志)、Read View(读视图) 和 隐藏的事务字段。以下是具体实现步骤和原理: 1. 核心数据结构 InnoDB 的每一行数据(…...
递归实现组合型枚举(DFS)
从 1∼n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。 输入格式 两个整数 n,m,在同一行用空格隔开。 输出格式 按照从小到大的顺序输出所有方案,每行 1 个。 首先,同一行内的数升序排列,相邻两个数用一个空格隔开。…...
【Java学习日记18】:三元运算符和运算符的优先级
一、三元运算符 2. 示例代码 例题1: 例题2: 二、运算符优先级 1. 优先级规则 Java 运算符的执行顺序由优先级决定,优先级高的先执行。 只要记住小括号优先级最大即可,以后就用这玩意 四、总结 运算符优先级:小括号 () 是最高优先级工具...
基于springboot放松音乐在线播放系统(源码+lw+部署文档+讲解),源码可白嫖!
摘要 本放松音乐在线播放系统采用B/S架构,数据库是MySQL,网站的搭建与开发采用了先进的Java进行编写,使用了Spring Boot框架。该系统从两个对象:由管理员和用户来对系统进行设计构建。前台主要功能包括:用户注册、登录…...
【Scratch编程系列】Scratch编程软件界面
Scratch是一款由麻省理工学院(MIT) 设计开发的少儿编程工具。其特点是:使用者可以不认识英文单词,也可以不使用键盘,就可以进行编程。构成程序的命令和参数通过积木形状的模块来实现。用鼠标拖动指令模块到脚本区就可以了。 这个软…...
技术驱动革新,强力巨彩LED软模组助力创意显示
随着LED显示技术的不断突破,LED软模组因其独特的柔性特质和个性化显示效果,正逐渐成为各类应用场景的新宠。强力巨彩软模组R3.0H系列具备独特的可塑造型能力与技术创新,为商业展示、数字艺术、建筑装饰等领域开辟全新视觉表达空间。 LED…...
历年跨链合约恶意交易详解(三)——Nomad Bridge20220801
漏洞合约函数 /*** notice Given formatted message, attempts to dispatch* message payload to end recipient.* dev Recipient must implement a handle method (refer to IMessageRecipient.sol)* Reverts if formatted messages destination domain is not the Replicas d…...
Tensorflow、Pytorch与Python、CUDA版本的对应关系(更新时间:2025年4月)
更新时间:20250405 一、Tensorflow与Python 、CUDA版本对应关系 注意:从 TF 2.11 开始,Windows 不支持 CUDA 构建。要在 Windows 上使用 TensorFlow GPU,您需要在 WSL2 中构建/安装 TensorFlow 或将 tensorflow-cpu 与 TensorFlow-DirectML-Plugin 一起使用 1.1、CPU版本…...
FPGA实现按键切换流水灯不同亮灭模式
本文是一位fpga新手学习fpga的博客,写出这个shi山代码花了3个小时左右,途中学习了按键消抖、状态机等知识... 实现目标:通过按键控制led灯亮的不同模式,将每种模式用状态机表达。 代码如下: module led(input btn1,in…...