【leetcode】 438. Find All Anagrams in a String

梦里梦外; 2023-08-17 16:34 117阅读 0赞

# 题目说明 #

[438. 找到字符串中所有字母异位词][438.]  
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

# 解法1 #

思路：滑动窗口。将字符串中的元素及个数保存在数组中。维护一个长度与非空字符串相同的滑动窗口，窗口滑动时，将新添加到窗口的字母个数加1，移出窗口的字母个数减1。通过比较两数组（窗口数组与目标字符串数组）来判断是否是异位词。  
时间复杂度：O(n)

vector<int> findAnagrams(string s, string p) {
      vector<int> vret;
      if (s.size() < p.size())
        return vret;
    
      vector<int> vm(26);
      vector<int> vn(26);
      for (int i = 0; i < p.size(); i ++)
      {
        vm[p[i] - 'a'] ++;
        vn[s[i] - 'a'] ++;
      }
    
      int l = 0, r = p.size() - 1;
    
      while(r < s.size())
      {
        if (vm == vn)
        {
          vret.push_back(l);
        }
    
        if (r + 1 < s.size())
        {
          vn[s[r + 1] - 'a'] ++;
          vn[s[l] - 'a'] --;
          l ++;
          r ++;
        }
        else
          break;
      }
      return vret;
    }

转载于:https://www.cnblogs.com/JesseTsou/p/11334127.html

[438.]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

发表评论取消回复

表情：

评论列表（有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读

相关【leetcode】 438. Find All Anagrams in a String

题目说明 [438. 找到字符串中所有字母异位词][438.] 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起

梦里梦外;/ 2023年08月17日 16:34/ 0 赞/ 118 阅读

相关 438. Find All Anagrams in a String(同元素异构造得起始点)

题目: 给定一个字符串小号和非空字符串p，找到所有开始指数p的中字谜小号。字符串仅包含小写英文字母，字符串s和p的长度均不得大于20,100。输出顺序无关紧要。

╰+攻爆jí腚メ/ 2023年02月12日 11:26/ 0 赞/ 42 阅读

相关 Leetcode 438. Find All Anagrams in a String

文章作者：Tyan 博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1] 1. Description ![Find All

迈不过友情╰/ 2022年09月09日 00:13/ 0 赞/ 97 阅读

相关 leetcode 438. Find All Anagrams in a String | 438. 找到字符串中所有字母异位词（Java）

题目 [https://leetcode.com/problems/find-all-anagrams-in-a-string/][https_leetcode.com_

柔情只为你懂/ 2022年09月04日 05:50/ 0 赞/ 166 阅读

相关 leetcode 438. Find All Anagrams in a String

1.题目 Given a string s and a non-empty string p, find all the start indices of p’s ana

痛定思痛。/ 2022年06月08日 00:05/ 0 赞/ 166 阅读

相关 leetcode 438. Find All Anagrams in a String 一个简单的移动窗口问题

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in

客官°小女子只卖身不卖艺/ 2022年06月04日 09:17/ 0 赞/ 131 阅读

相关 leetcode 438. Find All Anagrams in a String 滑动窗口法

[题目链接][Link 1] ![这里写图片描述][70] 解析主要使用滑动窗口法解题，需要好好体会的是中间的两个判断couter的用法，这里很巧妙。如果想

╰半夏微凉°/ 2022年05月26日 07:07/ 0 赞/ 164 阅读

相关 LeetCode：438. Find All Anagrams in a String（找出相同的子串的下标）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

阳光穿透心脏的1/2处/ 2022年04月11日 10:53/ 0 赞/ 136 阅读

相关 lc438. Find All Anagrams in a String

1. Find All Anagrams in a String Easy 1613 125 Favorite Share Given a string s and

小鱼儿/ 2022年01月12日 01:55/ 0 赞/ 197 阅读

相关 LeetCode : 438. Find All Anagrams in a String 查找所有异位字符串

试题 Given a string s and a non-empty string p, find all the start indices of p’s anagra

偏执的太偏执、/ 2021年06月24日 16:11/ 0 赞/ 301 阅读