438. Find All Anagrams in a Strin
2024-09-28 23:28:35
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". 本题开始的时候并没有想用O(n)的时间复杂度做出来,而是用了O(mn)的时间复杂度做,看了答案才知道本题是sliding window的变体,是two pointer的例子,不是很难,代码如下:
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<Integer>();
if(s==null||s.length()==0||p==null||p.length()==0) return res;
int left = 0,right = 0;
int count =p.length();
int[] word = new int[256];
for(int i=0;i<p.length();i++){
word[p.charAt(i)]++;
}
while(right<s.length()){
if(word[s.charAt(right++)]-->=1) count--;
if(count==0) res.add(left);
if(right-left==p.length()&&word[s.charAt(left++)]++>=0) count++;
}
return res;
}
}
最新文章
- 自己写的一个Pager分页组件,WebForm,Mvc都适用
- mybatis配置自带缓存和第三方缓存
- Android源码目录结构详解(转载)
- ubuntu14.04 archive sources.list
- 苹果的软件/系统盘 网站 http://www.panduoduo.net/u/bd-369186934/2
- 修改input的type属性
- js 创建书签小工具之理论
- Nginx 之并发优化
- 显示Title和隐藏Title的ListView
- zookeeper数据弱一致性
- PHP新手必须掌握的入门与实战技巧
- MSMQ队列学习记录
- jsp隐藏关键 敏感信息,只显示前后字段
- Redis在Windows中安装方法
- select下拉框插件jquery.editable-select
- SpringBoot整合elasticsearch
- Lucene入门学习
- 遍历DOM树,获取父节点
- kafka 数据一致性-leader,follower机制与zookeeper的区别;
- CSS html标签元素分类