LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)

栏目: Java · 发布时间: 5年前

内容简介:原题地址:这道题一开始看起来可能满头雾水,但是仔细想想,跟第76题也蛮像的,无非是这个变位词跟原词是长度相等的。这样就变成了固定宽度的滑动窗口了,不过我们刚才固定和变化的例子都看了,其实除了循环体结构略有不同,其他差异不大。然后就是匹配的条件不同,但是仔细一想,其实也差不多,就是那些我们在p里面的字符出现的频率也要一样。而且如果我们用固定宽度来做的话,我们会发现,我们不用检测有没有多余的字符,宽度一样,且频率一样的话,肯定没有多余的字符,所以这个代码可以轻松地从一个第76题的代码改造出来。

原题地址: https://leetcode.com/problems/find-all-anagrams-in-a-string/

要求

给定一个字符传s和一个非空字符串p,找到所有的p的变位词(anagrams,字符都一样,字符出现的位置不同)在s中的位置。仅包含小写英文单词,而且s和p的长度都不会超过20100。结果顺序不重要。

例 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”的变位词。

这道题一开始看起来可能满头雾水,但是仔细想想,跟第76题也蛮像的,无非是这个变位词跟原词是长度相等的。这样就变成了固定宽度的滑动窗口了,不过我们刚才固定和变化的例子都看了,其实除了循环体结构略有不同,其他差异不大。

然后就是匹配的条件不同,但是仔细一想,其实也差不多,就是那些我们在p里面的字符出现的频率也要一样。而且如果我们用固定宽度来做的话,我们会发现,我们不用检测有没有多余的字符,宽度一样,且频率一样的话,肯定没有多余的字符,所以这个代码可以轻松地从一个第76题的代码改造出来。

我写的比较粗糙,但是基本元素是类似的。首先函数开始和初始化(包括字符数组的初始化,count的初始化):

LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)

循环体(因为是固定宽度的窗口,所以,出入成对,代码很简单。)

LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)

第76题,会做了的话,这道题很简单吧,我的解法耗时6毫秒。

本题代码地址为: https://github.com/tinyfool/leetcode/tree/master/src/p0438

本文假设你对滑动窗口概念有所了解,如果你对滑动窗口的概念不够了解,请参看我介绍 滑动窗口的文章,里面有详细的解释


以上所述就是小编给大家介绍的《LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Chinese Authoritarianism in the Information Age

Chinese Authoritarianism in the Information Age

Routledge / 2018-2-13 / GBP 115.00

This book examines information and public opinion control by the authoritarian state in response to popular access to information and upgraded political communication channels among the citizens in co......一起来看看 《Chinese Authoritarianism in the Information Age》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具