当前位置:网站首页>LeetCode 438. 找到字符串中所有字母异位词__滑动窗口
LeetCode 438. 找到字符串中所有字母异位词__滑动窗口
2022-07-01 10:42:00 【向光.】
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 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" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
Solution1(直白滑窗):
显然这题我们可以使用滑动窗口来解决,即直接维护p字符串长度的窗口,每当窗口满时就判断一下窗口内的各种字母数量是否和p的一致即可。
Code1:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] hash = new int[26];
int winLen = p.length();
for(int i=0;i<winLen;i++){
char c = p.charAt(i);
hash[c - 'a']++;
}
List<Integer> res = new ArrayList<>();
List<Integer> window = new ArrayList<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(window.size() < winLen){
window.add(i);
}
else{
check(res,winLen,window,hash,s);
window.remove((int)0);
i--;
}
}
if(window.size() < winLen){
return res;
}
check(res,winLen,window,hash,s);
return res;
}
public void check(List<Integer> res,int winLen,List<Integer> window,int[] hash,String s){
int[] hashTemp = new int[26];
for(int k=0;k<winLen;k++){
Integer index = window.get(k);
hashTemp[s.charAt(index) - 'a']++;
}
int j = 0;
for(;j<26;j++){
if(hash[j] != hashTemp[j])
break;
}
if(j == 26){
res.add(window.get(0));
}
}
}
Solution2(优化便捷滑窗):
我们可以不直接维护普通滑窗,因为我们发现上述方法一,由于是维护一个有序序列来模拟滑窗,后面还需要一个哈希数组来表示滑窗内含有的字母种类及数量,因此我们可以想只创建一次哈希数组即可,在滑窗滑出老元素和滑进新元素时直接在那一个哈希数组上进行修改就行。
接着我们发现,可以直接使用哈希数组代替滑窗的有序序列进行存储,只用两个下标来模拟滑窗即可,滑窗本身不需要存储内容,交给哈希数组存储即可。
Code2:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int slen = s.length();
int plen = p.length();
List<Integer> res = new ArrayList<>();
if(s.length() < p.length()){
return res;
}
int[] hash = new int[26];
int[] hashTemp = new int[26];
// 先给滑窗塞满
for(int i=0;i<plen;i++){
hash[p.charAt(i) - 'a']++;
hashTemp[s.charAt(i) - 'a']++;
}
if(Arrays.equals(hash,hashTemp)){
res.add(0);
}
// 维护滑窗的两个下标即可,一个头部,一个头部+滑窗长度即可
for(int i=0;i<slen - plen ;i++){
hashTemp[s.charAt(i) - 'a']--;
hashTemp[s.charAt(i + plen) - 'a']++;
if(Arrays.equals(hash,hashTemp)){
res.add(i+1);
}
}
return res;
}
}
边栏推荐
- 有大佬知道这是为啥吗?表结构都是刚直接复制的源表 mysql-cdc
- Have you learned the necessary global exception handler for the project
- Can MySQL CDC take out the op field
- Is it safe to do fund fixed investment on CICC securities?
- Programmers want to go to state-owned enterprises? The technology is backward and the salary is low. I can't find a job after lying flat for several years
- 基金管理人的合规管理
- Is it safe to open a stock account online in 2022? Is there any danger?
- Rising Stars in Plant Sciences (RSPS2022) Finalist科学演讲会(6.30晚9点)
- C# 一行代码计算文件的MD5值 - CodePlus系列
- In the new database era, don't just learn Oracle and MySQL
猜你喜欢
12 product management platforms that everyone is using
新一代云原生数据库的设计与实践
机器学习之线性回归详解
JD and Tencent renewed the three-year strategic cooperation agreement; The starting salary rose to 260000 yuan! Samsung sk of South Korea competes for salary increase to retain semiconductor talents;
云上“视界” 创新无限 | 2022阿里云直播峰会正式上线
【论文阅读】Trajectory-guided Control Prediction for End-to-end Autonomous Driving: A Simple yet Strong Ba
[.net6] use ml.net+onnx pre training model to liven the classic "Huaqiang buys melons" in station B
IDEA运行报错Command line is too long. Shorten command line for...
What a high commission! The new programmer's partner plan is coming. Everyone can participate!
使用强大的DBPack处理分布式事务(PHP使用教程)
随机推荐
C [byte array] and [hexadecimal string] mutual conversion - codeplus series
选择在中金证券上炒股开户可以吗?安全吗?
About database: how to avoid deadlock in gbase 8s
【邂逅Django】——(二)数据库配置
Is it safe to do fund fixed investment on CICC securities?
Superscalar processor design yaoyongbin Chapter 4 branch prediction -- Excerpt from subsection 4.1
《百年巨匠》数字藏品中奖名单公布
MySQL常用命令
Matplotlib data visualization Foundation
Design and practice of new generation cloud native database
华为HMS Core携手超图为三维GIS注入新动能
Button button clear border
MySQL common commands
JD and Tencent renewed the three-year strategic cooperation agreement; The starting salary rose to 260000 yuan! Samsung sk of South Korea competes for salary increase to retain semiconductor talents;
442. duplicate data in array
What if the win11 account is locked and unable to log in? Win11 account is locked and unable to log in
零基础入行软件测试必看,10年测试老鸟的良心建议(共15条)
Prefabricated dishes usher in the "golden age", who can lead the next trillion market
106. construct binary tree from middle order and post order traversal sequence
SQL SERVER2014删除数据库失败,报错偏移量0x0000...