[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)


相关推荐

  • Navicat15在线激活码【在线注册码/序列号/破解码】

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

  • IIC通信协议总结(详细说明完整过程)

    IIC通信协议总结(详细说明完整过程)IIC协议简介IIC(inter-integratedCircuit集成电路总线)总线支持设备之间的短距离通信,用于处理器和一些外围设备之间的接口,它需要两根信号线来完成信息交换。IIC的一个特殊工艺优势是微控制器只需要两个通用I/O引脚和软件即可控制芯片网络。IIC最早是飞利浦在1982年开发设计并用于自己的芯片上,一开始只允许100Khz、7-bit标准地址,1992年,IIC的第一个公共规范发行,增加了400Khz的快速模式以及10bit地址扩展。IIC协议IIC协议把传输的消息分为两种类型

  • java启动器_JAVA基础:Java 启动器如何查找类

    java启动器_JAVA基础:Java 启动器如何查找类Java启动器java将初始化Java虚拟机。虚拟机随即按以下顺序搜索和加载类:自举类-构成Java平台的类,包括rt.jar和i18n.jar中的类。扩展类-使用Java扩展机制的类。它们被捆绑为.jar文件,位于扩展目录中。用户类-开发人员和第三方定义的类,不使用扩展机制。在命令行上使用-classpath选项(常用方法)或使用CLASSPATH…

  • pipeline和baseline是什么?

    pipeline和baseline是什么?昨天和刚来项目的机器学习小白解释了一边什么baseline和pipeline,今天在这里总结一下什么是baseline和pipeline。1.pipeline1.1从管道符到pipeline

  • 信贷风控模型搭建及核心风控模式分类

    信贷风控模型搭建及核心风控模式分类一、当前风控模式现状近年来,信用风险管理发展呈现出数据化、模型化、系统化、自动化和智能化的特点。传统的人工专家经验正逐步被模型与算法替代。因此,科技较为领先的金融服务公司会选择采用模型方式完成对借款人的自动评估与审批。目前,对于信贷审核来说主要基于的风控模式为IPC、信贷工厂、大数据三种,每一种都有自己不同的侧重点。二、最核心的风控模式分类1.IPC模式IPC模式起源于德国邮储银行,该模…

  • 腾讯云免费ssl_腾讯云ssl证书申请

    腾讯云免费ssl_腾讯云ssl证书申请1.点此进入SSL证书产品页面2.点击立即选购,进入产品配置界面。3.选择自定义配置–>国际标准–>域名型免费版,点击免费快速申请。4.进入登录界面,用微信扫二维码。5.填写域名相关信息,点击下一步6.选择域名的验证方式,推荐DNS验证,点击下一步。7.打开域名管理后台,根据上一步获得的域名解析信息,增加一条TXT类型的解析记录。8.回到腾讯云SSL证书申请界面,查看域名验证结果,验证成功会收到一条短信,反之会有提示错误。9.申

发表回复

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

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