《剑指 Offer》专项突破版 - 面试题 14 : 字符串中的变位词(C++ 实现)

2024-01-17 00:52

本文主要是介绍《剑指 Offer》专项突破版 - 面试题 14 : 字符串中的变位词(C++ 实现),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:LCR 014. 字符串的排列 - 力扣(LeetCode)

题目

输入字符串 s1 和 s2,如何判断字符串 s2 中是否包含字符串 s1 的某个变位词?如果字符串 s2 中包含字符串 s1 的某个变位词,则字符串 s1 至少有一个变位词是字符串 s2 的子字符串。假设两个字符串中只包含英文小写字母。例如,字符串 s1 为 "ac",字符串 s2 为 "dgcaf",由于字符串 s2 中包含字符串 s1 的变位词 "ca",因此输出 true。如果字符串 s1 为 "ab",字符串 s2 为 "dgcaf",则输出 false。

分析

变位词是与字符串相关的面试题中经常出现的一个概念。所谓的变位词是指组成各单词的字母及每个字母出现的次数完全相同,只是字母排列的顺序不同。例如 "pots"、"stops" 和 "tops" 就是一组变位词。

由变位词的定义可知,变位词具有以下几个特点。首先,一组变位词的长度一定相同;其次,组成变位词的字母集合一定相同,且每个字母出现的次数也相同

这个题目如果不考虑时间复杂度,用暴力法就可以解决。实际上,一个字符串的变位词是字符串的排列。可以先求出字符串 s1 的所有排列,然后判断每个排列是不是字符串 s2 的子字符串。

下面尝试寻找更高效的算法。

设字符串 s1 的长度为 m,字符串 s2 的长度为 n。这个题目实际上等价于判断字符串 s2 中是否存在长度为 m,且字符及其个数与字符串 s1 相同的子字符串

因此,我们先用哈希表统计字符串 s1 中每个字符出现的次数,由于这个题目强调字符串只包含英文小写字母,而英文小写字母的个数是确定的,一共 26 个,因此可以用数组模拟一个简单的哈希表。数组的下标 0 对应字母 'a',它的值对应字母 'a' 出现的次数。数组的下标 1 对应字母 'b',它的值对应字母 'b' 出现的次数。以此类推,数组的下标 25 对应字母 'z',它的值对应字母 'z' 出现的次数。

然后逐一判断字符串 s2 中长度为 m 的子字符串中的字符及其个数是否和 s1 相同。判断方法就是扫描子字符串中的每个字符,把该字符在哈希表中对应的值减 1,如果哈希表中所有的值是 0,那么该子字符串就是字符串 s1 的一个变位词

代码实现

class Solution {
public:bool areAllZero(const vector<int>& counts){for (int count : counts){if (count != 0)return false;}return true;}bool checkInclusion(string s1, string s2) {int m = s1.size(), n = s2.size();if (m > n)return false;vector<int> counts(26, 0);for (int i = 0; i < m; ++i){++counts[s1[i] - 'a'];--counts[s2[i] - 'a'];}// 判断 s2 中前 m 个字符组成的子字符串是否为 s1 的变位词if (areAllZero(counts))return true;// 逐个判断 s2 中其余长度为 m 的子字符串是否为 s1 的变位词for (int i = m; i < n; ++i)  // 注意:i 指向子字符串的最后一个字符{++counts[s2[i - m] - 'a'];--counts[s2[i] - 'a'];if (areAllZero(counts))return true;}return false;}
};

该算法的时间复杂度是 O(m + 26n),即 O(m + n);空间复杂度是 O(1)

这篇关于《剑指 Offer》专项突破版 - 面试题 14 : 字符串中的变位词(C++ 实现)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/614454

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount