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

每日一练:找到字符串中所有字母异位词

一、题目要求

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母

二、解法1-框取比较 O(N) 效率低

用一个 vector<int> v保存p子串的字符种类(下标)和对应数量(值),以 s 中每一个字符为起点,保存size(p的字符数)个字符,最后比较tmp 与 v 是否相等,相等就纳入返回值中。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int size = p.size();vector<int> v(26,0);for (const auto e : p) {v[e-'a']++;}for (int i = 0; i + size <= s.size(); i++) {vector<int> tmp(26,0);int j = 0;for (; j < size; j++) {if (v[s[i+j]-'a'] == 0) // 优化{i = i + j;break;}tmp[s[i + j]-'a']++;}if (j == size)if (v == tmp) {ret.push_back(i);}}return ret;}
};

         

三、解法2-滑动窗口 O(N)

维护一个滑动窗口,窗口初始化后先进行一次比较,之后窗口每次向后滑动一位,比较一次。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;vector<int> slid_window(26,0); // 滑动窗口vector<int> standard(26,0);    // 比较标准if(s.size() < p.size())return ret;for(int i = 0;i < p.size();i++) // 初始化比较标准和滑动窗口{standard[p[i]-'a']++;slid_window[s[i]-'a']++;}if(standard == slid_window)   // 先进行一次比较{ret.push_back(0);}for(int i = 0;i+p.size() < s.size();i++){// 窗口后移1位slid_window[s[i]-'a']--; // 去掉窗口第一个元素slid_window[s[i+p.size()]-'a']++; // 得到下一个元素if(standard == slid_window) // 比较是否相同{ret.push_back(i+1);}}return ret;}
};

优化:

在解法2的基础上用一个 记录器 count 记录滑动窗口中的字符的数量与种类和目标子串的关系:

每有一个字符的数量或者不同,对应下标的值就不是0,differ就+1。

我们可以用以下逻辑实现:

(1)将 p 中的所有字符记录在 count 中,每有一个字符就自减1

(2)初始化滑动窗口中的字符,每有一个字符就自增1

(3)初始化目前的differ

(4)窗口向后滑动,失去的字符就自减,得到的字符串自加,如果使记录器中的0减少或者增多就更新differ

(5)每次滑动后就判断 differ ,等于0就往答案插入滑动窗口目前的起始下标

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;if (s.size() < p.size())return ret;int differ = 0;                    // 记录不同的字符种类数目vector<int> count(26, 0);          // 记录器for (int i = 0; i < p.size(); i++) // 初始化计数器{count[p[i] - 'a']--;count[s[i] - 'a']++;}for (int i = 0; i < count.size(); i++) { // 初始化differif (count[i] != 0)differ++;}if (differ == 0) // 先进行一次判断{ret.push_back(0);}for (int i = 0; i + p.size() < s.size(); i++) {// 窗口后移1位if (count[s[i] - 'a'] == 1) // 不同变相同differ--;else if (count[s[i] - 'a'] == 0) // 相同变不同differ++;count[s[i] - 'a']--;if (count[s[i + p.size()] - 'a'] == -1) // 不同变相同differ--;else if (count[s[i + p.size()] - 'a'] == 0) // 相同变不同differ++;count[s[i + p.size()] - 'a']++;if (differ == 0) // 比较是否相同{ret.push_back(i + 1);}}return ret;}
};


http://www.mrgr.cn/news/20938.html

相关文章:

  • 微软RD客户端 手机 平板 远程控制 Windows桌面
  • 【2024国赛B题】高教杯全国大学生数学建模国赛建模过程+完整代码论文全解全析
  • ffmpeg音视频开发从入门到精通——ffmpeg下载编译与安装
  • 在 Linux 上以 All-in-One 模式安装 KubeSphere
  • SAP ABAP 程序迁移工具 SAPLINK ABAP GIT
  • Docker进入容器运行命令及查看docker容器日志
  • vue ts 本地缓存数据
  • html 单页面路由模式hash和history
  • 用fastapi搭建cpca地址提取服务接口
  • [一文讲透] STM32实现ADC转换并使用DMA传输
  • 鸿蒙轻内核M核源码分析系列八 静态内存MemoryBox
  • k8s上搭建devops环境
  • 99%的Java程序员不知道的Java Instrument
  • tkinter中按比例放大
  • HTTP与HTTPS在软件测试中的解析
  • SpringBoot项目用Aspose-Words将Word转换为PDF文件正常显示中文的正确姿势
  • 在深度学习计算机视觉的语义分割中,Boundary和Edge的区别是?
  • 波导模式分析2 用于圆TE01模式高功率传输线的大型多模波导滤波器
  • 【新闻转载】2024年上半年勒索软件态势分析:团伙数量激增,攻击策略多样化
  • 大模型日报|9 篇必读的大模型论文