[LeetCode]Find All Anagrams in a String

[LeetCode]Find All Anagrams in a String

大家好,又见面了,我是全栈君。

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 s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

1.解题思路

anagrams,就是只顺序不同但个数相同的字符串,那我们就可以利用hashtable的思想来比较每个字符串中字符出现的个数是否相等。
对于两个字符串我们分别准备数组(大小为256)来存储每个字符出现的次数:
1) 对于p,我们遍历,并在hp中记录字符出现的次数;
2) 之后遍历s,先把当前字符的个数+1,但是需要考虑当前index是否已经超过了p的长度,如果超过,则表示前面的字符已经不予考虑,所以要将index-plen的字符的个数-1;最后判断两个数组是否相等,如果相等,返回index-plen+1,即为开始的下标。

2.代码

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res=new ArrayList<Integer>();
        if(s.length()==0||s==null||p.length()==0||p==null) return res;
        int[] hs=new int[256];
        int[] hp=new int[256];
        int plen=p.length();
        for(int i=0;i<plen;i++){
            hp[p.charAt(i)]++;
        }
        for(int j=0;j<s.length();j++){
            hs[s.charAt(j)]++;
            if(j>=plen){
                hs[s.charAt(j-plen)]--;
            }
            if(Arrays.equals(hs,hp))
                res.add(j-plen+1);
        }
        return res;
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108772.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python 学习笔记 列表 xxx XXX

    Python 学习笔记 列表 xxx XXXPython学习笔记列表xxxXXXbicycles=[‘trek’,’cannondale’,’redline’,’specialized’]print(bicycles)print(bicycles[0])print(bicycles[0].title())print(bicycles[-1])names=[‘wenwen’,’juanjuan’,’yuyu’]forxinnames: prin…

  • navicat premium 15 激活码 mac【在线注册码/序列号/破解码】「建议收藏」

    navicat premium 15 激活码 mac【在线注册码/序列号/破解码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 时序数据库介绍_时序数据库公司

    时序数据库介绍_时序数据库公司首先,什么是时序数据? ​ 简单来说,时序数据就是按照时间维度索引的数据,比如车辆轨迹数据,传感器温度数据。随着物联网时代的到来,时序数据的数据量呈井喷式爆发,针对于这一数据细分的优化存储显得越来越重要。01什么是InfluxDBInfluxDB是一个开源的、高性能的时序型数据库,在时序型数据库DB-EnginesRanking上排名第一。在介绍InfluxDB之前,先来介绍下时序数据。按照时间顺序记录系统、设备状态变化的数据被称为时序数据(TimeSeriesData),如.

  • a was not declared_zeroifnull

    a was not declared_zeroifnull[size=medium]ibatis:isNotEmpty:过滤空串""和空nullisNotNull:只过滤空nullphp:isset:过滤null和未定义isEmpty:过滤false、空串""、nullExp SELECTLPM.WORK_TYPE"workType", LPM.DE…

  • dism失败 ox800f0818_Win 10 DISM 一直失败,错误: 0x8000ffff – Microsoft Community[通俗易懂]

    dism失败 ox800f0818_Win 10 DISM 一直失败,错误: 0x8000ffff – Microsoft Community[通俗易懂]你好!了解到您的问题。在使用RestoreHealth命令时是需要在检测出系统出现问题且映像文件可修复的情况下才能使用;Dism/Online/Cleanup-Image/ScanHealth这条命令将扫描全部系统文件并和官方系统文件对比,扫描计算机中的不一致情况。Dism/Online/Cleanup-Image/CheckHealth这条命令必须在前一条命令执行完以后,发现系统文件…

  • 第一次数学危机_圆周率的诡异现象

    第一次数学危机_圆周率的诡异现象咋看标题,是不是很懵,??数学还有危机,Areukiddingme?!哈哈,当然只是人们对数学的认识的一种突破性的发展的一种描述。那么,我们在之前的描述中,都是在整数的这个范畴。因为在生活的过

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号