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

LeetCode[中等] 438. 找到字符串中所有字母异位词

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

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

思路:滑动窗口

  1. s包含p的异位词 ——> 则s.Length > p.Length;反之,s不包含p的异位词,返回空数组。
  2. s.Length >= p.Length,需要遍历 s 的每个长度为 p 长度的子字符串,判断是否存在子字符串是 p 的异位词。比较每个字符的出现次数,判断每个子字符串是否为 p 的异位词。
  3. 首先遍历 p 计算每个字符的出现次数,然后遍历 s 的首个子字符串并计算每个字符的出现次数。
  4. 每次将子字符串的下标范围向右移动一位,则有一个字符移出子字符串,有一个字符移入子字符串,更新子字符串中这两个字符的出现次数之后,比较子字符串中的每个字符的出现次数是否与 p 中的每个字符的出现次数相同。
    public class Solution {
        public IList<int> FindAnagrams(string s, string p) {
            IList<int> startIndices = new List<int>();
            int sLength = s.Length, pLength = p.Length;
            if(sLength < pLength)
                return startIndices;
            int[] sCounts = new int[26];
            int[] pCounts = new int[26];
            for(int i = 0; i < pLength; i++)
            {
                char c1 = s[i];
                sCounts[c1 - 'a']++;
                char c2 = p[i];
                pCounts[c2 - 'a']++;
            }
            if (CheckEqual(sCounts, pCounts)) {
                startIndices.Add(0);
            }
            for(int i = pLength; i < sLength; i++)
            {
                char prev = s[i - pLength];//上一次的窗口第一个元素
                sCounts[prev - 'a']--;
                char curr = s[i];//末尾元素
                sCounts[curr - 'a']++;
                if (CheckEqual(sCounts, pCounts)) {
                    startIndices.Add(i - pLength + 1);
                }
            }
            return startIndices;
        }
            public bool CheckEqual(int[] sCounts, int[] pCounts) 
            {
                for (int i = 0; i < 26; i++)
                {
                    if (sCounts[i] != pCounts[i]) {
                    return false;
                }
            }
            return true;
        }
    }

    复杂度分析

  • 时间复杂度:O((m+n)×∣Σ∣),其中 m 和 n 分别是字符串 s 和 p 的长度,Σ 是字符集,这道题中 Σ 是全部小写英语字母,∣Σ∣=26。只有当 s 的长度大于等于 p 的长度时才需要遍历字符串 s 寻找 p 的异位词,需要遍历字符串 s 和 p 各一次,对于每个子字符串需要 O(∣Σ∣) 的时间判断是否为 p 的异位词。
  • 空间复杂度:O(∣Σ∣),其中 Σ 是字符集,这道题中 Σ 是全部小写英语字母,∣Σ∣=26。记录 p 和 s 中每个字母的出现次数需要 O(∣Σ∣) 的空间。


http://www.kler.cn/a/310130.html

相关文章:

  • 卸载一直显示在运行的应用
  • LLM时代下Embedding模型如何重塑检索、增强生成
  • 【C++】详细介绍模版进阶,细节满满
  • LED和QLED的区别
  • 中兴光猫修改SN,MAC,修改地区,异地注册,改桥接,路由拨号
  • Lodash的常用方法整理
  • 【嵌入式硬件】续流二极管
  • 前端常用的服务器推送技术
  • python 环境问题
  • 828华为云征文|云服务器Flexus X实例|Ubunt部署Vue项目
  • 使用python来保存键盘输入情况,可保存到sqlite3数据库
  • Nginx 负载均衡:优化网站性能与可扩展性的利器
  • 使用rust自制操作系统内核
  • 需要申请 TAC
  • 「C++系列」异常处理
  • Apache Spark — Repartition 与 Coalesce(调整数据集分区)
  • 【软件测试】压力测试的学习总结
  • 作业帮大数据面试题及参考答案
  • Linux shell编程学习笔记81:zcat命令——快速查看压缩文件内容
  • 函数题 6-10 阶乘计算升级版【PAT】
  • IOS 25 实现歌单详情(UITableView)列表 ②
  • 即插即用 | YOLOv8热力图可视化方法详解
  • MySQL的(DDL、DCL、DQL、DML)语言学习
  • 7.7opencv中(基于C++) 翻转图像
  • 完全解决git clone超时和git子模块无法下载问题
  • CSS学习路线