Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-02-05 12:33:57
438. Find All Anagrams in a String
给你一个字串s和p,若s的某个子字串可以由p的字符排列后得到,返回s的子字串第一个
字符的索引值。
Example :
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
s[0:2]="cba" 可以被p组合所以加入0
s[6:8]="bac" 可以被p组合所以加入6
思路:
1.首先,若p的长度大于s则必不存在解,所以可以直接返回。
2.因为p可以任意排列所以我们只关心他的字母数量,我们可以维护一个基于s的
滑动窗口,每次加入一个元素,如果s的字母数量大于p就把最左边的字母从窗口
去除并更新窗口左边界,直到窗口的字母数量小于等于目标数量。
3.如果窗口的大小刚好等于p那就表示有一个子字串满足条件,将left加入结果集,
当右边的指标跑完s就可以得到解了。
Java Code:
作者: pandix (面包屌)   2023-02-05 12:35:00
大师
作者: SecondRun (雨夜琴声)   2023-02-05 12:39:00
跟昨天那题好像

Links booklink

Contact Us: admin [ a t ] ucptt.com