type
status
date
slug
summary
tags
category
icon
password
创建时间
Nov 11, 2024 02:30 PM
字节 - 2024/11/1
给定两个字符串 s 和 t,找到 s 中第一个 t 的异位词的子串。
示例 1:
输入: s = "adcabcbabcd", t = "abc"
输出: "cab"
解释:
异位词:两个字符串中出现的字符种类以及各字符出现的次数相同。
起始索引等于 2 的子串是 "cab", 它是 "abc" 的异位词, 且是 s 中第一个出现。
242. 有效的字母异位词
给定两个字符串
s
和 t
,编写一个函数来判断 t
是否是 s
的字母异位词。字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语,并使用所有原字母一次。
方法一:直接暴力做。最最暴力,两个哈希表,验证“你中有我,我中有你”。
方法二:使用数组模拟哈希表,然后逐个元素比较。
方法三:
参考 灵茶山艾府
438. 找到字符串中所有字母异位词
给定两个字符串
s
和 p
,找到 s
中所有 p
的异位词的子串,返回这些子串的起始索引。不考虑答案输出的顺序。方法一:暴力做法。每次从
s
的一个位置开始,遍历 p
中元素,是否满足。不满足就直接跳出。
方法二:滑动窗口
我们想一想,上面的暴力做法为什么会超时呢?因为我们做了太多的无用功,我们前一次做过了判断,第二次遇到了还是需要判断。举个例子:

我们在遍历的时候,重复判断了
d
两次,我们第二次判断完全可以跳过 d
,从下一个位置开始。有了上面这个例子,我们再想想有哪些情况,是我们需要跳过的。- 有多余的元素;

- 有不存在的元素(就是我们上面例子的情况)
而上面的这两种情况,在我们中代码有一个相同的表现,就是我们统计的字符在减去他们所表示的字符,数量会小于零。因此,我们开始位置就可以确定了,我们可以找出没有出现上述表现的位置作为新的起始点就可以了啊。
如此,在代码中的表现就是滑动窗口了。我先右移右指针,如果出现上面的表现,我们就右移左指针,不让其出现这种表现。
如果窗口大小恰好等于
p
的字符串长度,完美,加入到我们答案中。因此,重写编写代码