当前位置: 首页 > news >正文

力扣每日一题30:串联所有单词的子串

题目描述

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd""cdabef", "cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] 和 s 由小写英文字母组成

请问您在哪类招聘中遇到此题?

1/5

社招

校招

实习

未遇到

通过次数

196.5K

提交次数

502.9K

通过率

39.1%

思路一,暴力遍历,通过178/179

字典(字符串数组)里每个单词的长度是固定的,假设字典里有word_num个单词,每个单词的长度为word_size。那么我们的任务就是在s中找到所有长度为word_num*word_size的子串,判断这个子串能不能由字典里的单词串联起来(其中串联指的是words里面的任意一个排列的连接)。

这个方法的代码比较好写,先用一个哈希表存放字典中每个单词出现的次数。每次判断子串时再创键一个新表,遍历word_num个单词,若某个单词在旧表中没有出现过或者是新表出现次数比旧表的多,就说明这个子串不符合条件。

实现代码:

class Solution {
public:unordered_map<string,int> mp;bool judge(string& s,int wordNumber,int wordLength,int begin)//单词个数,单词的字母个数{unordered_map<string,int> newMp;for(int i=begin;i<begin+wordNumber*wordLength;i+=wordLength){string temp=s.substr(i,wordLength);if(mp.find(temp)==mp.end()) return false;//字符串数组中没出现newMp[temp]++;if(newMp[temp]>mp[temp]) return false;//多出现了}return true;}vector<int> findSubstring(string s, vector<string>& words) {vector<int> ans;for(int i=0;i<words.size();i++){mp[words[i]]++;}int n=words.size(),m=words[0].size(),ls=s.length();int left=0,right=n*m;for(int i=0;i<=ls-n*m;i++){bool flag=judge(s,n,m,i);if(flag) ans.push_back(i);}return ans;}
};

思路二:哈希表+滑动窗口+类KMP思想,全部通过

我们学过kmp算法的都知道,在字符串匹配时(假设是在s串里寻找s1串),如果比较懂s为下标i,s1为下标j的位置时发现两个串暂时不相等,用BF算法的思想来说i要返回到i-j+1的位置,j要回到0的位置(这里假设下标从0开始),然后重新匹配。

但是按照kmp算法的思想来说,既然s1已经比到了下标  j  的位置,那么说明s1的前 j 个字符和s[i]的前j个字符是相等的,而如果s1的最前面 k 个字符和s[i]的前 k 个字符相等的话,i就不用回溯,而 j 只需要回溯到第 k+1 个位置就行。

总而言之,kmp算法最核心的思想就是保留了之前搜索时的信息,方便下一次搜索。

代码:

 

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ans;int word_nums = words.size();int word_size = words[0].size();int ls = s.length();unordered_map<string, int> mp1;for (int i = 0; i < word_nums; i++)mp1[words[i]]++;for (int i = 0; i < word_size; i++){int k;unordered_map<string, int> mp2;bool flag = false;//表示同一个i下,上次匹配成功for (int j = i; j + word_nums * word_size <= ls; j += word_size){//从下标j开始的子串if (!flag) k = j;for (; k < j + word_nums * word_size; k += word_size){string temp = s.substr(k, word_size);if (mp1.find(temp) == mp1.end()) {//下标k之前(包括下标k)开始的子串都不用判断了j = k;//j=k+word_size;外层的循环j还会加一次word_size//之前存储的结果也作废了flag = false;mp2.clear();break;}else {mp2[temp]++;//重复次数过多时,从下表j开始就不行了//重复出现的子串是temp,所以只要从j开始寻找第一次出现temp的位置index,然后从index+word_size开始匹配if (mp2[temp] > mp1[temp]) {int index = j;string t = s.substr(index, word_size);while (t != temp) {index += word_size;mp2[t]--;t = s.substr(index, word_size);}j = index + word_size;//index+=word_size;外层循环会加一次word_sizemp2[temp]--;}}}//从j开始的子串完全匹配if (k == j + word_nums * word_size){ans.push_back(j);//移除从j开始的子串的第一个单词string t = s.substr(j, word_size);mp2[t]--;if (mp2[t] == 0) mp2.erase(t);//k += word_size;//只有一个单词没有匹配好,所以从k就从k+word_size开始flag = true;}}}return ans;}
};

相关文章:

力扣每日一题30:串联所有单词的子串

题目描述 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 words ["ab","cd","ef"]&#xff0c; 那么 &q…...

vim | vim的快捷命令行

快捷进入shell界面 -> :nnoremap <F8> :sh<CR> -> 绑定到了F8 :nnoremap <F8> :sh<CR> 快捷执行 -> :nnoremap <F5> :wa<CR>:!g % -o a.out && ./a.out<CR> -> 绑定到了F5 :nnoremap <F5> :wa<CR>…...

项目管理平台-01-BugClose 入门介绍

拓展阅读 Devops-01-devops 是什么&#xff1f; Devops-02-Jpom 简而轻的低侵入式在线构建、自动部署、日常运维、项目监控软件 代码质量管理 SonarQube-01-入门介绍 项目管理平台-01-jira 入门介绍 缺陷跟踪管理系统&#xff0c;为针对缺陷管理、任务追踪和项目管理的商业…...

web集群-lvs-DR模式基本配置

目录 环境&#xff1a; 一、配置RS 1、安装常见软件 2、配置web服务 3、添加vip 4、arp抑制 二、配置LVS 1、添加vip 2、安装配置工具 3、配置DR 三、测试 四、脚本方式配置 1、LVS-DR 2、LVS-RS 环境&#xff1a; master lvs 192.168.80.161 no…...

基于深度学习的面部情绪识别算法仿真与分析

声明&#xff1a;以下内容均属于本人本科论文内容&#xff0c;禁止盗用&#xff0c;否则将追究相关责任 基于深度学习的面部情绪识别算法仿真与分析 摘要结果分析1、本次设计通过网络爬虫技术获取了七种面部情绪图片&#xff1a;吃惊、恐惧、厌恶、高兴、伤心、愤怒、自然各若…...

C语言经典面试题目(十六)

1、什么是C语言中的指针常量和指针变量&#xff1f;它们有什么区别&#xff1f; 在C语言中&#xff0c;指针常量和指针变量是指针的两种不同类型。它们的区别在于指针的指向和指针本身是否可以被修改。 指针常量&#xff1a;指针指向的内存地址不可变&#xff0c;但指针本身的…...

【C语言】文件操作揭秘:C语言中文件的顺序读写、随机读写、判断文件结束和文件缓冲区详细解析【图文详解】

欢迎来CILMY23的博客喔&#xff0c;本篇为【C语言】文件操作揭秘&#xff1a;C语言中文件的顺序读写、随机读写、判断文件结束和文件缓冲区详细解析【图文详解】&#xff0c;感谢观看&#xff0c;支持的可以给个一键三连&#xff0c;点赞关注收藏。 前言 欢迎来到本篇博客&…...

JAVA八股文面经问题整理第6弹

文章目录 目录 文章目录 提问问题 问题1 问题2 问题3 问题4 问题5 问题6 问题7 问题8 问题9 问题10 问题11 问题12 写在最后 提问问题 介绍一下Linux常⽤命令&#xff0c;例如&#xff1a;Vim快捷键&#xff0c;常⽤查看Log的命令&#xff0c;路径相关&#x…...

pytest相关面试题

pytest是什么&#xff1f;它有什么优点&#xff1f; pytest是一个非常流行的Python测试框架&#xff0c;它具有简洁、易用、高校等优点。他可以帮助测试人员方便地编写和运行测试用例&#xff0c;并且提供了丰富的插件和扩展&#xff0c;支持各种测试需求介绍下pytest常用的库 …...

Keras库搭建神经网络

Keras并非简单的神经网络库&#xff0c;而是一个基于Theano的强大的深度学习库&#xff0c;利用它不仅仅可以搭建普通的神经网络&#xff0c;还可以搭建各种深度学习模型&#xff0c;如自编码器、循环神经网络、递归神经网络、卷积神经网络等。 安装代码&#xff1a; pip ins…...

适配器模式与桥接模式-灵活应对变化的两种设计策略大比拼

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 &#x1f680; 转载自&#xff1a;设计模式深度解析&#xff1a;适配器模式与桥接模式-灵活应对变…...

Elasticsearch8搭建及Springboot中集成使用

1.搭建 1.1.下载地址 Elasticsearch&#xff1a;https://www.elastic.co/cn/downloads/elasticsearch Kibana&#xff1a;https://www.elastic.co/cn/downloads/kibana 1.2.具体过程 下载安装包&#xff1a;访问上述链接&#xff0c;下载适合你操作系统的Elasticsearch和Ki…...

asp.net在线租车平台

说明文档 运行前附加数据库.mdf&#xff08;或sql生成数据库&#xff09; 主要技术&#xff1a; 基于asp.net架构和sql server数据库 功能模块&#xff1a; asp.net在线租车平台 用户功能有首页 行业新闻用户注册车辆查询租车介绍访问后台 后台管理员可以进行用户管理 管…...

Beamer模板——基于LaTeX制作学术PPT

Beamer模板——基于LaTeX制作学术PPT 介绍Beamer的基本使用安装和编译用于学术汇报的模板项目代码模板效果图 Beamer的高级特性动态效果分栏布局定理环境 介绍 在学术领域&#xff0c;演示文稿是展示和讨论研究成果的重要方式。传统的PowerPoint虽然方便&#xff0c;但在处理复…...

性能测试-Jmeter中IF控制器使用

一、Jmeter控制器 分为两种类型&#xff1a; 控制测试计划执行过程中节点的逻辑执行顺序&#xff0c;如&#xff1a;循环控制器&#xff0c;if控制器等对测试计划中的脚本进行分组&#xff0c;方便Jmeter统计执行结果以及进行脚本的运行时控制等&#xff0c;如&#xff1a;吞…...

华为综合案例-普通WLAN全覆盖配置(2)

组网图 结果验证 在AC_1和AC_2上执行display ap all命令&#xff0c;检查当前AP的状态&#xff0c;显示以下信息表示AP上线成功。[AC_1] display ap all Total AP information: nor : normal [1] ExtraInfo : Extra information P : insufficient power supply ---…...

这里是一本关于 DevOps 企业级 CI/CD 实战的书籍...

文章目录 &#x1f4cb; 前言&#x1f3af; 什么是 DevOps&#x1f3af; 什么是 CI/CD&#x1f3af;什么是 Jenkins&#x1f9e9; Jenkins 简单案例 &#x1f3af; DevOps 企业级实战书籍推荐&#x1f525; 参与方式 &#x1f4cb; 前言 企业级 CI/CD 实战是一个涉及到软件开发…...

机器学习 - save和load训练好的模型

如果已经训练好了一个模型&#xff0c;你就可以save和load这模型。 For saving and loading models in PyTorch, there are three main methods you should be aware of. PyTorch methodWhat does it do?torch.saveSaves a serialized object to disk using Python’s pickl…...

【动态规划】【同余前缀和】【多重背包】[推荐]2902. 和带限制的子多重集合的数目

本文涉及知识点 动态规划汇总 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 C算法&#xff1a;滑动窗口总结 多重背包 LeetCode2902. 和带限制的子多重集合的数目 给你一个下标从 0 开始的非负整数数组 nums 和两个整数 l 和 r 。 请你…...

nginx介绍及搭建

架构模型 Nginx是由一个master管理进程、多个worker进程组成的多进程模型。master负责管理worker进程&#xff0c;worker进程负责处理网络事件&#xff0c;整个框架被设计为一种依赖事件驱动、异步、非阻塞的模式。 优势&#xff1a; 1、充分利用多核&#xff0c;增强并发处理…...

告别道路预测老套路:用ParkPredict+模型思路,解决停车场里的‘鬼探头’难题

破解泊车场景预测困局&#xff1a;ParkPredict模型的技术革新与实践停车场里的每一次转向、倒车和避让&#xff0c;都是对自动驾驶系统预测能力的极限挑战。与开放道路的规则明确不同&#xff0c;这里没有清晰的车道线指引&#xff0c;没有统一的行驶方向&#xff0c;只有随时可…...

录音会议纪要整理不同使用场景,实用口碑选择建议

针对不同场景的录音整理需求&#xff08;短录音、中长录音、长内容深度整理&#xff09;&#xff0c;本文基于实际使用体验&#xff0c;分享不同场景下的工具选择建议与使用心得。一、场景一&#xff1a;短录音&#xff08;15-60分钟&#xff0c;发音清晰&#xff09;典型场景&…...

中兴光猫终极管理指南:解锁工厂模式与Telnet权限的实战教程

中兴光猫终极管理指南&#xff1a;解锁工厂模式与Telnet权限的实战教程 【免费下载链接】zteOnu A tool that can open ZTE onu device factory mode 项目地址: https://gitcode.com/gh_mirrors/zt/zteOnu 掌握中兴光猫的设备管理和权限获取能力是网络管理员和技术爱好者…...

保姆级避坑指南:在Ubuntu 22.04上搞定ROS2 Humble、PX4与Gazebo的联合仿真(附Empy版本降级)

保姆级避坑指南&#xff1a;Ubuntu 22.04下ROS2 Humble与PX4联合仿真的21个关键陷阱当你在Ubuntu 22.04上第一次尝试搭建ROS2 Humble、PX4与Gazebo的联合仿真环境时&#xff0c;可能会遇到比预期更多的挑战。这不是一个简单的"复制粘贴命令就能完成"的任务——版本冲…...

告别DLL缺失烦恼!Visual C++运行库合集一键搞定Windows应用依赖问题

告别DLL缺失烦恼&#xff01;Visual C运行库合集一键搞定Windows应用依赖问题 【免费下载链接】vcredist AIO Repack for latest Microsoft Visual C Redistributable Runtimes 项目地址: https://gitcode.com/gh_mirrors/vc/vcredist 你是否曾经在打开某个软件或游戏时…...

BetterNCM安装器终极指南:5分钟解锁网易云音乐无限潜能

BetterNCM安装器终极指南&#xff1a;5分钟解锁网易云音乐无限潜能 【免费下载链接】BetterNCM-Installer 一键安装 Better 系软件 项目地址: https://gitcode.com/gh_mirrors/be/BetterNCM-Installer 你是否觉得网易云音乐PC版功能有限&#xff0c;界面单调&#xff1f…...

纯硬件实现I2C协议:从逻辑门到传感器通信的深度实践

1. 项目概述&#xff1a;用纯硬件“解剖”I2C总线很多朋友在玩传感器&#xff0c;尤其是温湿度传感器时&#xff0c;都绕不开I2C这个通信协议。市面上绝大多数的教程和方案&#xff0c;都会告诉你&#xff1a;找个单片机&#xff08;比如Arduino、STM32&#xff09;&#xff0c…...

数字合成器d-FORMANT:从模拟经典到数字复刻的工程实践

1. 项目概述&#xff1a;从模拟经典到数字复刻如果你对合成器稍有了解&#xff0c;或者对电子音乐制作背后的硬件感兴趣&#xff0c;那么“FORMANT”这个名字你一定不陌生。它最初是上世纪70年代由《Elektor》杂志发布的一款模拟单音合成器&#xff0c;以其清晰的模块化设计和出…...

模式分层预测驱动推断:处理复杂缺失数据的统计新框架

1. 项目概述&#xff1a;当数据“缺胳膊少腿”时&#xff0c;如何做出靠谱的推断&#xff1f;在数据科学和统计建模的日常工作中&#xff0c;我们最怕遇到什么&#xff1f;不是复杂的算法&#xff0c;也不是海量的数据&#xff0c;而是数据本身“缺胳膊少腿”——也就是缺失值。…...

如何用WaveTools终极优化鸣潮游戏体验:从帧率解锁到抽卡分析的完整指南

如何用WaveTools终极优化鸣潮游戏体验&#xff1a;从帧率解锁到抽卡分析的完整指南 【免费下载链接】WaveTools &#x1f9f0;鸣潮工具箱 项目地址: https://gitcode.com/gh_mirrors/wa/WaveTools 如果你正在玩《鸣潮》却经常遇到帧率不稳定、画面卡顿或者抽卡记录混乱的…...