力扣LeetCode: 2506 统计相似字符串对的数目
题目:
给你一个下标从 0 开始的字符串数组 words
。
如果两个字符串由相同的字符组成,则认为这两个字符串 相似 。
- 例如,
"abca"
和"cba"
相似,因为它们都由字符'a'
、'b'
、'c'
组成。 - 然而,
"abacba"
和"bcfd"
不相似,因为它们不是相同字符组成的。
请你找出满足字符串 words[i]
和 words[j]
相似的下标对 (i, j)
,并返回下标对的数目,其中 0 <= i < j <= words.length - 1
。
示例 1:
输入:words = ["aba","aabb","abcd","bac","aabc"] 输出:2 解释:共有 2 对满足条件: - i = 0 且 j = 1 :words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。 - i = 3 且 j = 4 :words[3] 和 words[4] 只由字符 'a'、'b' 和 'c' 。
示例 2:
输入:words = ["aabb","ab","ba"] 输出:3 解释:共有 3 对满足条件: - i = 0 且 j = 1 :words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。 - i = 0 且 j = 2 :words[0] 和 words[2] 只由字符 'a' 和 'b' 组成。 - i = 1 且 j = 2 :words[1] 和 words[2] 只由字符 'a' 和 'b' 组成。
示例 3:
输入:words = ["nba","cba","dba"] 输出:0 解释:不存在满足条件的下标对,返回 0 。
提示:
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i]
仅由小写英文字母组成
解法:
解决思路
-
提取字符集合:
-
对于每个字符串,提取其中包含的字符种类(去重)。
-
例如,
"aba"
的字符集合是{'a', 'b'}
,"aabb"
的字符集合也是{'a', 'b'}
。
-
-
比较字符集合:
-
如果两个字符串的字符集合相同,则它们相似。
-
例如,
"aba"
和"aabb"
的字符集合都是{'a', 'b'}
,因此它们相似。
-
-
统计相似对数:
-
对于所有字符串,统计具有相同字符集合的字符串数量。
-
如果有
k
个字符串具有相同的字符集合,则这些字符串之间可以形成C(k, 2)
对相似对(即从k
个字符串中选 2 个的组合数)。
-
实现步骤
-
提取字符集合:
-
对每个字符串,将其字符去重并排序,生成一个唯一的标识符(例如,将字符集合转换为字符串)。
-
例如,
"aba"
的字符集合是{'a', 'b'}
,可以转换为字符串"ab"
。
-
-
统计字符集合的出现次数:
-
使用哈希表(
unordered_map
)记录每个字符集合的出现次数。 -
例如,
"ab"
出现 2 次,"abc"
出现 1 次。
-
-
计算相似对数:
-
对于哈希表中的每个字符集合,如果有
k
个字符串具有相同的字符集合,则这些字符串之间可以形成k * (k - 1) / 2
对相似对。 -
将所有字符集合的相似对数累加,得到最终结果。
-
代码实现
class Solution {
public:int similarPairs(vector<string>& words) {unordered_map<string, int> countMap;// 遍历每个字符串,提取字符集合并统计for (const string& word : words) {string charSet = getCharSet(word);countMap[charSet]++;}int result = 0;// 计算满足条件的下标对数量for (const auto& pair : countMap) {int k = pair.second;if (k >= 2) {result += k * (k - 1) / 2;}}return result;}private:string getCharSet(const string& word) {vector<char> chars(word.begin(), word.end());sort(chars.begin(), chars.end());chars.erase(unique(chars.begin(), chars.end()), chars.end());return string(chars.begin(), chars.end());}
};
代码详细解释
-
getCharSet
函数:-
输入:一个字符串
word
。 -
输出:该字符串的字符集合(去重并排序后的字符串)。
-
实现步骤:
-
将字符串转换为字符数组
chars
。 -
对字符数组排序(
sort
)。 -
去重(
unique
和erase
)。 -
将字符数组转换为字符串并返回。
-
示例:
-
输入:
"aba"
-
输出:
"ab"
-
-
similarPairs
函数:-
输入:字符串数组
words
。 -
输出:满足条件的下标对数量。
-
实现步骤:
-
遍历每个字符串,调用
getCharSet
获取字符集合。 -
使用哈希表
countMap
统计每个字符集合的出现次数。 -
遍历哈希表,计算每个字符集合的相似对数,并累加到结果中。
-
示例:
-
输入:
["aba", "aabb", "abcd", "bac", "aabc"]
-
哈希表内容:
{"ab": 2, "abcd": 1, "abc": 2}
-
计算结果:
C(2, 2) + C(2, 2) = 1 + 1 = 2
-
复杂度分析
-
时间复杂度:
-
提取字符集合:对于每个字符串,排序和去重的复杂度为
O(m log m)
,其中m
是字符串的平均长度。 -
统计哈希表:遍历所有字符串的复杂度为
O(n)
,其中n
是字符串的数量。 -
计算相似对数:遍历哈希表的复杂度为
O(n)
。 -
总时间复杂度:
O(n * m log m)
。
-
-
空间复杂度:
-
哈希表
countMap
的空间复杂度为O(n)
。 -
字符集合的空间复杂度为
O(m)
。 -
总空间复杂度:
O(n * m)
。
-
示例运行
示例 1:
输入:words = ["aba", "aabb", "abcd", "bac", "aabc"]
-
提取字符集合:
-
"aba"
->"ab"
-
"aabb"
->"ab"
-
"abcd"
->"abcd"
-
"bac"
->"abc"
-
"aabc"
->"abc"
-
-
统计哈希表:
-
{"ab": 2, "abcd": 1, "abc": 2}
-
-
计算相似对数:
-
"ab"
出现 2 次 ->C(2, 2) = 1
-
"abc"
出现 2 次 ->C(2, 2) = 1
-
总相似对数:
1 + 1 = 2
-
输出:2
示例 2:
输入:words = ["aabb", "ab", "ba"]
-
提取字符集合:
-
"aabb"
->"ab"
-
"ab"
->"ab"
-
"ba"
->"ab"
-
-
统计哈希表:
-
{"ab": 3}
-
-
计算相似对数:
-
"ab"
出现 3 次 ->C(3, 2) = 3
-
总相似对数:
3
-
输出:3
示例 3:
输入:words = ["nba", "cba", "dba"]
-
提取字符集合:
-
"nba"
->"abn"
-
"cba"
->"abc"
-
"dba"
->"abd"
-
-
统计哈希表:
-
{"abn": 1, "abc": 1, "abd": 1}
-
-
计算相似对数:
-
每个字符集合只出现 1 次,无法形成相似对。
-
总相似对数:
0
-
输出:0
总结
通过提取字符集合、统计哈希表,并计算组合数,我们可以高效地解决这个问题。代码的时间复杂度和空间复杂度都在合理范围内,能够处理题目中的最大输入规模。
相关文章:
力扣LeetCode: 2506 统计相似字符串对的数目
题目: 给你一个下标从 0 开始的字符串数组 words 。 如果两个字符串由相同的字符组成,则认为这两个字符串 相似 。 例如,"abca" 和 "cba" 相似,因为它们都由字符 a、b、c 组成。然而,"aba…...
DeepSeek模型量化
技术背景 大语言模型(Large Language Model,LLM),可以通过量化(Quantization)操作来节约内存/显存的使用,并且降低了通讯开销,进而达到加速模型推理的效果。常见的就是把Float16的浮…...
如何调整CAN位宽容忍度?
CAN位宽容忍度是指在控制器局域网络(CAN, Controller Area Network)中允许时钟同步的误差范围。这是CAN网络正常通信时的关键因素之一,因为CAN协议依赖位同步来确保多个节点在总线上正确解码数据。CAN位宽容忍度确保节点之间由于时钟偏差或抖…...
Versal - 基础6(Linux 开发 AIE-ML + 自动化脚本解析)
目录 1. 简介 2. 步骤解析 2.1 概览 2.1.1 步骤依赖关系 2.1.2 总目录结构 2.2 Vitis XPFM 2.2.1 Dir 2.2.2 Makefile 2.2.3 vitis_pfm.py 2.3 Kernels 2.3.1 Dir 2.3.2 Makefile 2.3.3 config 文件 2.4 AIE_app 2.4.1 Dir 2.4.2 Makefile 2.4.3 aie 要点 2.…...
乐享数科:供应链金融—三个不同阶段的融资模式
供应链金融是与产业链紧密结合的融资模式,它主要体现在订单采购、存货保管、销售回款这三个不同的业务阶段,并针对这些阶段提供了相应的金融服务。以下是这三个阶段中主要的融资模式及其特点: 供应链金融融资模式主要分为以下几种࿱…...
vmware虚拟机Ubuntu Desktop系统怎么和我的电脑相互复制文件、内容
1、先安装vmware workstation 17 player,然后再安装Ubuntu Desktop虚拟机,然后再安装vmware tools,具体可以参考如下视频: VMware虚拟机与主机实现文件共享,其实一点也不难_哔哩哔哩_bilibili 2、本人亲自试过了&…...
【React】React 基础(2)
JSX 是什么 JSX是一种 JavaScript 的语法扩展(extension), 也在很多地方称之为 JavaScript XML, 因为看起就是一段XML语法。它用于描述我们的Ul界面,并且其完成可以和 JavaScript 融合在一起使用; 为什么 React 选择使用 jsx? React 认为渲…...
DeepSeek接入Siri(已升级支持苹果手表)完整版硅基流动DeepSeek-R1部署
DeepSeek接入Siri(已升级支持苹果手表)完整版硅基流动DeepSeek-R1部署 **DeepSeek** 是一款专注于深度学习和人工智能的工具或平台,通常与人工智能、机器学习、自动化分析等领域有关。它的主要功能可能包括:深度学习模型搜索&…...
ASP.NET MVC AJAX 文件上传
如何使用 MVC 5 和 AJAX(.NET Framework)上传文件。 使用AJAX和ASP.NET MVC 上传文件 再简单不过了。对于最纯粹的人来说,这不需要使用jQuery。此代码实际上允许上传多个文件。 注意:以下代码示例支持 ASP.NET MVC 5。如果使用 .…...
npm使用了代理,但是代理软件已经关闭导致创建失败
如果在关闭前打开了vscode,此时vscode中的终端没有刷新,就会出现这个问题,最开始会一直转圈圈,直到超时,然后出现该报错 ❯ npm create vuelatest npm error code ECONNREFUSED npm error syscall connect npm error …...
Spring Boot定时任务原理
Spring Boot定时任务原理 在现代应用中,定时任务的调度是实现周期性操作的关键机制。Spring Boot 提供了强大的定时任务支持,通过注解驱动的方式,开发者可以轻松地为方法添加定时任务功能。本文将深入探讨 Spring Boot 中定时任务的实现原理…...
公文派2025:免费社区版重大安装更新!
大家好,感谢对「公文派」的支持。 距离上一次更新已经过去了将近一年的时间,今天我们带来了全新的免费2025社区版,该版本也是目前最新的版本,无需授权即可使用所有的功能。 我们先来看下本版本的更新及特色功能 聚合多个AI功能…...
Ubuntu24.04LTS的下载安装超细图文教程(VMware虚拟机及正常安装)
😸个人主页👉:神兽汤姆猫 📖系列专栏:开发语言环境配置 、 Java学习 、Java面试 、Markdown等 学习上的每一次进步,均来自于平时的努力与坚持。 💕如果此篇文章对您有帮助的话,请点…...
ES6相关操作
一.JavaScript的基础语法 1.Demo1.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>JavaScrip…...
【运维】源码编译安装cmake
背景: 已经在本地源码编译安装gcc/g,现在源码安装cmake 下载源码 下载地址:CMake - Upgrade Your Software Build System 安装步骤: ./bootstrap --prefix/usr/local/cmake make make install 错误处理 1、提示找不到libmpc.…...
代码随想录_回溯
代码随想录_回溯 回溯 77.组合 77. 组合 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 思路: 回溯 优化: 剪枝 注意代码中i,就是for循环里选择的起始位置。 for (int i startIndex; i <…...
tauri2实现监听记住窗口大小变化,重启回复之前的窗口大小
要想实现记住窗口大小的功能,整体逻辑就是要监听窗口大小变化,将窗口大小保存下来,重启之后,读取保存的大小,然后恢复。这里可以使用rust层实现,也可以在前端实现。我这里就纯rust层实现了。 监听窗口变化…...
番茄工作法html实现
对比了deepseek-r1-online和本地部署的14b的版本,输出的输出的html页面。 在线满血版的功能比较强大,可以一次完成所有要求。14b版本的功能有一些欠缺,但是基本功能也是写了出来了。 input write a html named Pomodoro-clock which “hel…...
C++:dfs,bfs各两则
1.木棒 167. 木棒 - AcWing题库 乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 5050 个长度单位。 然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。 请你设计一个程序…...
【ORB-SLAM3】鲁棒核函数的阈值设置
问题背景 阈值 δ \delta δ 是 Huber 鲁棒核函数的重要参数。首先给出结论,在ORB-SLAM系列中,该阈值选取的原则为: 单目情况下,根据95%置信水平下两自由度卡方检验的临界值, δ \delta δ 设置为 5.991 \sqrt{5.9…...
四种常见图形库GLUT,SDL,SFML和GLFW简介
GLUT、SDL、SFML 和 GLFW 是四种常用的库,用于管理窗口、输入和上下文创建,通常与 OpenGL 结合使用以实现图形渲染。以下是它们的详细介绍、常用应用场合和具体案例。 1. GLUT(OpenGL Utility Toolkit) 简介 GLUT 是一个用于创建…...
C++类和对象进阶:初始化列表和static成员深度详解
C类和对象:初始化列表和static成员深度详解 1. 前言2. 构造函数初始化成员变量的方式2.1 构造函数体内赋值2.2 初始化列表2.2.1 初始化列表的注意事项 2.3 初始化列表的初始化顺序 3. 类的静态成员3.1 引入3.2 静态成员变量3.3 静态成员函数3.4 静态成员的注意事项3…...
[C#]C# winform部署yolov12目标检测的onnx模型
yolov12官方框架:github.com/sunsmarterjie/yolov12 【测试环境】 vs2019 netframework4.7.2 opencvsharp4.8.0 onnxruntime1.16.3 【效果展示】 【调用代码】 using System; using System.Collections.Generic; using System.ComponentModel; using System.…...
阿里云k8s服务部署操作一指禅
文章目录 DockerFile镜像操作阿里云k8s服务部署 DockerFile # 使用 JDK 17 官方镜像 # linux架构:FROM --platformlinux/amd64 openjdk:17-jdk-slim # arm架构:openjdk:17-jdk-slim FROM --platformlinux/amd64 openjdk:17-jdk-slim# 设置工作目录 WORK…...
Transformer LLaMA
一、Transformer Transformer:一种基于自注意力机制的神经网络结构,通过并行计算和多层特征抽取,有效解决了长序列依赖问题,实现了在自然语言处理等领域的突破。 Transformer 架构摆脱了RNNs,完全依靠 Attention的优…...
球队训练信息管理系统设计与实现(代码+数据库+LW)
摘 要 传统办法管理信息首先需要花费的时间比较多,其次数据出错率比较高,而且对错误的数据进行更改也比较困难,最后,检索数据费事费力。因此,在计算机上安装球队训练信息管理系统软件来发挥其高效地信息处理的作用&a…...
【存储中间件API】MySQL、Redis、MongoDB、ES常见api操作及性能比较
常见中间件api操作及性能比较 ☝️ MySQL crud操作✌️ maven依赖✌️ 配置✌️ 定义实体类✌️ 常用api ☝️ Redis crud操作✌️ maven依赖✌️ 配置✌️ 常用api ☝️ MongoDB crud操作✌️ maven依赖✌️ 配置文件✌️ 定义实体类✌️ MongoDB常用api ☝️ ES crud操作 ⭐️…...
UE_C++ —— Gameplay Classes
目录 一,Adding Classes 二,Class Headers Class Declaration Class Specifiers Metadata Specifiers 三,Class Implementation Class Constructor 引擎中每个游戏类都由一个类头文件(.h)和一个类源文件&#x…...
windows上vscode cmake工程搭建
安装vscode插件: 1.按装fastc(主要是安装MinGW\mingw64比较方便) 2.安装C,cmake,cmake tools插件 3.准备工作完成之后,按F1,选择cmake:Quick Start就可以创建一个cmake工程。 4.设置Cmake: G…...
软件测试:1、单元测试
1. 单元测试的基本概念 单元(Unit):软件系统的基本组成单位,可以是函数、模块、方法或类。 单元测试(Unit Testing):对软件单元进行的测试,验证代码的正确性、规范性、安全性和性能…...
如果后台的Long类型的数据返回是null,那么Android客户端的数据bean的kotlin的Long类型的字段接受到数据后是null空指针吗?
如果后台的Long类型的数据返回是null,那么Android客户端的数据bean的kotlin的Long类型的字段接受到数据后是null空指针吗? DeepSeek R1 思考 35 秒 思考过程 好的,用户的问题是关于在Android客户端使用Kotlin处理后台返回的Long类型数据为n…...
Vue3 打造 Windows 桌面个性高效组件工具
软件介绍 Widgets 这款基于 Vue3 构建的开源 Windows 桌面小部件工具超实用。 其多样化组件库涵盖超 20 种,从倒计时、打工进度等实用工具,到抖音热榜等实时资讯组件应有尽有,各组件独立运行,满足多场景需求。 高度自定义布局支持…...
学习笔记-沁恒第四讲-米醋
一, 语音模块:数据包发送 刷卡模块:数据包接收 AS608:数据包发送接收 二,第三讲文件夹改成第四讲,工程也改成第四讲 三,目前在内存里面。保存新值,掉电会丢失 u8 password[6]{1,…...
epoll_event的概念和使用案例
epoll_event 是 Linux 下 epoll I/O 多路复用机制的核心数据结构,用于描述文件描述符(File Descriptor, FD)上发生的事件及其关联的用户数据。通过 epoll,可以高效地监控多个文件描述符的状态变化(如可读、可写、错误等…...
容器和虚拟机选择对比
1. 概述 如果主要需求是学习和测试 Ubuntu 下的命令行工具或服务型应用,推荐使用 Docker Docker 更轻量、更高效,适合快速搭建和销毁环境。 启用 WSL 2,Docker Desktop 是一个非常好的选择。 如果需要完整的桌面环境或进行复杂的系统级开…...
C++17中std::chrono::duration和std::chrono::time_point的舍入函数
文章目录 1. std::chrono::duration的舍入函数1.1 floor1.2 ceil1.3 round 2. std::chrono::time_point的舍入函数2.1 示例 3. 舍入函数的应用场景3.1 时间测量3.2 数据记录3.3 时间同步 4. 总结 在C17中, std::chrono库提供了一组强大的时间处理工具,包…...
基于SpringBoot的线上汽车租赁系统的设计与实现(源码+SQL脚本+LW+部署讲解等)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
基于Dancing Links的精确覆盖算法(解决NP难问题)和量子计算机模拟中的Shor算法(涉及数论与量子叠加态模拟)
一、Dancing Links算法实现数独求解(NP难问题) 算法方案 数独可转化为精确覆盖问题,使用Knuth提出的DLX算法实现高效求解。该算法通过双向十字循环链表实现快速回溯,时间复杂度可达O(n^k)(k为常数) #include <iostream> #include <vector> #include <c…...
体育品牌排行榜前十名:MLB·棒球1号位
MLB是一个融合了棒球文化与街头时尚元素的潮流运动品牌。以下是对该品牌的详细介绍: 一、品牌背景 • 全称:MLB全称是Major League Baseball,即美国职业棒球大联盟。不过,作为品牌的MLB并非由美国职业棒球大联盟直接运营&#x…...
Java网络编程封装
系列文章目录 Java知识点 文章目录 系列文章目录👉前言👉一、封装的目标👉二、套接字层封装👉壁纸分享👉总结 👉前言 Java 网络编程封装原理主要围绕着将底层的网络通信细节隐藏起来,提供简洁…...
数字内容体验标杆案例解析
内容概要 在数字化转型浪潮中,数字内容体验正成为企业构建核心竞争力的关键抓手。本文通过拆解金融、零售、文旅等领域的标杆案例,系统分析沉浸式设计与智能交互系统的技术融合路径,揭示头部企业如何通过XR技术、实时数据可视化及场景化内容…...
区块链相关方法-PEST分析
一、定义:一种用于分析企业外部宏观环境的工具。PEST 这四个字母分别代表政治(Political)、经济(Economic)、社会(Social)和技术(Technological)。这种分析方法帮助企业或组织了解宏…...
Dify安装教程:Linux系统本地化安装部署Dify详细教程
1. 本地部署 Dify 应用开发平台 环境:Ubuntu(24.10) docker-ce docker compose 安装 克隆 Dify 源代码至本地环境: git clone https://github.com/langgenius/dify.git 启动 Dify: cd dify/docker cp .env.example...
git使用-克隆远程项目、分支管理
文章目录 克隆远程项目到本地1. 远程找到需要克隆的项目,复制ssh地址2. idea开启git版本控制(如果已经开了,忽略此步骤)3. clone远端项目4. 克隆完成 分支管理1. 新建分支2. 切换分支3. 合并分支4. 储存变化 克隆远程项目到本地 …...
QT 引入Quazip和Zlib源码工程到项目中,无需编译成库,跨平台,压缩进度
前言 最近在做项目时遇到一个需求,需要将升级的文件压缩成zip,再进行传输; 通过网络调研,有许多方式可以实现,例如QT私有模块的ZipReader、QZipWriter;或者第三方库zlib或者libzip或者quazip等࿱…...
SQLMesh 系列教程8- 详解 seed 模型
在数据分析和建模过程中,外部模型(External Models)在 SQLMesh 中扮演着重要角色。外部模型允许用户引用外部数据源或现有数据库表,从而实现灵活的数据整合和分析。本文将介绍外部模型的定义、生成方法(包括使用 CLI 和…...
oracle apex post接口
日常记录 使用到了apex_json方式接收 、、、1 首先,接口通过body传递过来,成功接收到, 数据格式为 JSON_OBJECT_T l_json : JSON_OBJECT_T.parse(:body); 这里我用参数接收到 然后 里面是包含了 "data" 我用 继续接收到这个 l…...
复制所绑定元素文本的vue自定义指令
最近写了一个复制所绑定元素文本的vue自定义指令,给大家分享一下。 import { ElMessage } from element-plus// data-* 属性名 const dataCopyBtnTextAttribute data-copy-btn-text // 复制按钮的class,结合项目实际进行设置 const copyBtnClass icon…...
若依-@Excel新增注解numberFormat
Excel注解中原本的scale会四舍五入小数,导致进度丢失 想要的效果 显示的时候保留两个小数真正的数值是保留之前的数值 还原过程 若以中有一個專門的工具类,用来处理excel的 找到EXCEL导出方法exportExcel()找到writeSheet,写表格的方法找到填充数据的方法…...
内容中台重构智能服务:人工智能技术驱动精准决策
内容概要 现代企业数字化转型进程中,内容中台与人工智能技术的深度融合正在重构智能服务的基础架构。通过整合自然语言处理、知识图谱构建与深度学习算法三大技术模块,该架构实现了从数据采集到决策输出的全链路智能化。在数据层,系统可对接…...