首页 > 其他分享 >LeetCode 热题 100 之 438. 找到字符串中所有字母异位词

LeetCode 热题 100 之 438. 找到字符串中所有字母异位词

时间:2023-07-24 17:11:06浏览次数:38  
标签:子串 异位 热题 lenp ls 438 res ord 100

题目

给定两个字符串 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 * 10^4
s 和 p 仅包含小写字母

思路

得到 s,p的长度lens,lenp,对字符串p进行排序。i从0开始0遍历s,找到字串i,i+lenp之间的字符串,并进行排序,如果和排序后的p串一样则满足条件记录下i的值

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        lens = len(s)
        lenp = len(p)
        res = []
        tempp = ''.join(sorted(p))
        for i in range(lens-lenp+1):
            temps = ''.join(sorted(s[i:i+lenp]))
            if(temps==tempp):
                res.append(i)
        return res
            
            

此方法中途排序耗时长,且存在较多重复操作

思路二

使用数组记录小写字母出现的次数。

代码二

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        lens = len(s)
        lenp = len(p)
        res = []
        if lenp>lens:
            return []
        ls = [0] *26
        lp = [0] * 26
        for i in range(lenp):
            lp[ord(p[i])-ord('a')]+=1
            ls[ord(s[i])-ord('a')]+=1
        if ls == lp:
            res.append(0)
        for l in range(lens-lenp):
            ls[ord(s[l])-ord('a')]-=1
            ls[ord(s[l+lenp])-ord('a')]+=1
            if ls==lp:
                res.append(l+1)
        return res

            
            

标签:子串,异位,热题,lenp,ls,438,res,ord,100
From: https://www.cnblogs.com/anamzingclown/p/17577754.html

相关文章

  • LeetCode 热题 100 之 3. 无重复字符的最长子串
    题目给定一个字符串s,请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其长度为1。示例3:......
  • 爬了1000张清纯妹子私房照,我流鼻血了...
    闲扯几句大家好,我是你们的老朋友青戈,之前分享了一篇Java爬虫的入门实战教程,收获了不少赞,看来大家伙对爬虫的热情度还是蛮高的哈。既然大家都这么想学爬虫,那今天就安排点刺激的。那你要非问我有多刺激,那我只能告诉,我看完…流鼻血了…......
  • android pageing 加载100调数据
    AndroidPaging加载100条数据的实现流程步骤概览以下是实现AndroidPaging加载100条数据的步骤概览:步骤描述1添加依赖2创建数据源3创建数据源工厂4创建分页配置5创建数据源观察者6创建分页加载器7创建适配器8在界面中使用分页加载器和......
  • nodejs sqlite报错 typeorm[ Expression tree is too large (maximum depth 1000)]
    最近在给公司开发一个工具时,使用SQLite,然后突然发现报错:(node:16195)UnhandledPromiseRejectionWarning:QueryFailedError:SQLITE_ERROR:Expressiontreeistoolarge(maximumdepth1000)athandler(/snapshot/server-work/node_modules/typeorm/driver/sqlite/Sql......
  • 显示前100个回文素数python
    回文素数的科普1.什么是回文数?回文数是指从左到右和从右到左读起来都一样的数。比如,121、12321等都是回文数。2.什么是素数?素数是指大于1且只能被1和自身整除的数。比如,2、3、5、7等都是素数。3.什么是回文素数?回文素数是同时满足回文数和素数的数。比如,131、373等都是回......
  • 100到200的素数
    #include<math.h>intmain(){ intcount=0; inti=0; for(i=101;i<=200;i+=2) { intj=1; intflag=1; for(j=2;j<sqrt(i);j++) { if(i%j==0) { flag=0; break; } } if(flag==1) { count++; printf("%d",i......
  • 滴滴太狠:分布式ID,如何达到1000Wqps?
    文章很长,且持续更新,建议收藏起来,慢慢读!疯狂创客圈总目录博客园版为您奉上珍贵的学习资源:免费赠送:《尼恩Java面试宝典》持续更新+史上最全+面试必备2000页+面试必备+大厂必备+涨薪必备免费赠送:《尼恩技术圣经+高并发系列PDF》,帮你实现技术自由,完成职业升级,薪......
  • c语言_练习实例100
     题1:1.有 1、2、3、4 四个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?#include<stdio.h>intmain(){for(inti=1;i<5;i++){//取百位for(intj=1;j<5;j++){//取十位for(intk=1;k<5;k++){//取个位if(i!=j&&j!......
  • [解题报告][CF1007E]Mini Metro
    Statement传送门有\(n\)个车站,从\(1\)到\(n\)编号,车站\(i\)初始有\(a_i\)个人。在每个小时结束的前几分钟,车站\(i\)会新增\(b_i\)个人。玩家有无限辆容量为\(k\)的火车。玩家在每个小时的中间(也就是\(\mathrm{30min,1h30min,2h30min...}\))可以让任意......
  • 【雕爷学编程】Arduino动手做(100)---MAX30102手腕心率模块2
    37款传感器与执行器的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的,这里准备逐一动手尝试系列实验,不管成功(程序走通)与否,都会记录下来—小小的进步或是搞......