首页 > 其他分享 >找到字符串中所有字母异位词

找到字符串中所有字母异位词

时间:2024-11-09 10:20:05浏览次数:4  
标签:子串 slist ab int 异位 字母 length 字符串

找到字符串中所有字母异位词

题目

给定两个字符串 sp,找到 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" 的异位词。

思路

  • 可以使用滑动数组的概念
  • 滑动数组的长度与p的长度相等,每向前一步,减掉原本数组中最前面的字符,新增正在遍历的字符,可以使用一个长度为26的数组来表示目前的滑动数组里各有多少个字符,然后与p(也生成一个长度为26的数组)相比,如果相同,就加入到结果集中。

实现代码

public List<Integer> findAnagrams(String s, String p) {
    if (s.length() < p.length()) return Collections.emptyList();
    List<Integer> result = new ArrayList<>();
    int[] slist = new int[26];
    int[] plist = new int[26];
    for (int i = 0; i < p.length(); i++) {
        slist[s.charAt(i) - 'a']++;
        plist[p.charAt(i) - 'a']++;
    }
    if (Arrays.equals(slist, plist)){
        result.add(0);
    }
    for (int i = 0; i < s.length() - p.length(); i++) {
        slist[s.charAt(i) - 'a']--;
        slist[s.charAt(i + p.length()) - 'a']++;
        if (Arrays.equals(slist, plist)){
            result.add(i + 1);
        }
    }
    return result;
}

标签:子串,slist,ab,int,异位,字母,length,字符串
From: https://www.cnblogs.com/wwgroup/p/18536399

相关文章

  • 算法专题:字符串
    目录1.最长公共前缀1.1算法原理1.2算法代码2.最长回文子串2.1算法原理2.2算法代码3.二进制求和3.1算法原理 3.2算法代码4.字符串相乘4.1算法原理 4.2算法代码1.最长公共前缀.-力扣(LeetCode)1.1算法原理有以下两种策略:两两进行比较统一......
  • 字符串类
    字符串类:构造string对象和初始化#include<iostream>#include<string>usingnamespacestd;intmain(){ strings;//空串 strings1="hello,hhh";//初始化为hello,hhh strings2("OK");//初始化为"OK" strings3(s1);//用s1初始化s3 strings4(4,'c&#......
  • 字符串类
    17.6字符串类字符串类string是不同于字符数组的字符串处理方式。使用字符串类,需要包含以下头文件:#include<string>在学习过程中,必须分清楚string类和字符数组处理字符串的异同。17.6.1字符串类:输入输出(cin/cout)可以使用cin和cout来读写string类型。使用cin读入string类型,会忽略......
  • byte数组转16进制,二进制字符串
    1)16进制字符串a)c#内置apibyte[]bytes=BitConverter.GetBytes(123);varhexStr=BitConverter.ToString(bytes); b)实现1///返回低字节顺序十六进制字符串(低字节在左侧)publicstaticstringToHexString(byte[]bytes){char[]hexChars="012345678......
  • 看一遍就会用——面向对象:类和对象,实例属性,实例方法,字符串表示
    python面向对象1.类和对象2.实例属性3.实例方法4.字符串表示1.__str__方法2.__repr__方法1.类和对象在Python中,类和对象是面向对象编程(OOP)的核心概念。类(Class)是创建对象的蓝图或模板,它定义了对象将拥有的属性和方法。对象(Object)则是根据类创建的具体实例,它包含了类......
  • 详解:字符串常量池
            字符串常量池是Java运行时环境(JRE)的一部分,它用于存储字符串字面量。字符串字面量是源代码中直接用双引号括起来的字符串,例如"hello"。在Java中,字符串是不可变的,这意味着一旦创建了一个字符串对象,它的值就不能改变。        当Java编译器遇到字符串字......
  • 前端入门一之JS对象、字符串对象、数组对象、Data()对象等
    前言JS是前端三件套之一,也是核心,本人将会更新JS基础、JS对象、DOM、BOM、ES6等知识点,这篇是JS常用的内置对象;这篇文章是本人大一学习前端的笔记;欢迎点赞+收藏+关注,本人将会持续更新。文章目录目录总览1、对象1.1、创建对象(object)利用字面量创建对象对象的调用变量......
  • 华为机试HJ29 字符串加解密
    首先看一下题描述对输入的字符串进行加解密,并输出。加密方法为:当内容是英文字母时则用该英文字母的后一个字母替换,同时字母变换大小写,如字母a时则替换为B;字母Z时则替换为a;当内容是数字时则把该数字加1,如0替换1,1替换2,9替换0;其他字符不做变化。解密方法为加密的逆过程。......
  • 华为机试HJ30 字符串合并处理
    首先看一下题描述按照指定规则对输入的字符串进行处理。详细描述:第一步:将输入的两个字符串str1和str2进行前后合并。如给定字符串"dec"和字符串"fab",合并后生成的字符串为"decfab"第二步:对合并后的字符串进行排序,要求为:下标为奇数的字符和下标为偶数的字符分别从......
  • FastAPI 查询参数与字符串校验详解:类型、校验规则与元数据设置
    FastAPI查询参数与字符串校验详解:类型、校验规则与元数据设置本文详细介绍了FastAPI中查询参数的设置与校验方法,涵盖了可选参数、默认值、必要参数和参数列表的处理方式。通过使用Query类,开发者可以为查询参数添加额外的校验规则,如最小长度、最大长度、正则表达式匹配......