welcome to my blog
LeetCode Top 100 Liked Questions 438. Find All Anagrams in a String (Java版; Medium)
题目描述
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".
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public List
<Integer> findAnagrams(String s
, String p
) {
List
<Integer> list
= new ArrayList<>();
HashMap
<Character, Integer> map
= new HashMap<>();
for(int i
=0; i
<p
.length(); i
++){
char ch
= p
.charAt(i
);
map
.put(ch
, map
.getOrDefault(ch
, 0)-1);
}
int left
=0, right
=0;
int count
= 0;
while(right
<s
.length()){
char ch
= s
.charAt(right
);
if(map
.containsKey(ch
)){
map
.put(ch
, map
.get(ch
)+1);
if(map
.get(ch
)==0){
count
++;
}
}
while(count
==map
.size()){
if(right
- left
+ 1 == p
.length()){
list
.add(left
);
}
char ch2
= s
.charAt(left
);
if(map
.containsKey(ch2
)){
map
.put(ch2
, map
.get(ch2
)-1);
if(map
.get(ch2
)==-1){
count
--;
}
}
left
++;
}
right
++;
}
return list
;
}
}
第一次做; 双指针法:先移动right,满足条件后,再移动left; count变量记录有多少个字符满足数量要求了; 判断两个Integer类型的变量是否相等,得用equals()方法!! 不能用==, 但是可以用<或者>
import java
.util
.ArrayList
;
import java
.util
.HashMap
;
class Solution {
public List
<Integer> findAnagrams(String s
, String p
) {
ArrayList
<Integer> res
= new ArrayList<>();
if(s
.length() < p
.length())
return res
;
HashMap
<Character, Integer> needs
= new HashMap<>();
HashMap
<Character, Integer> window
= new HashMap<>();
int count
= 0;
for(int i
=0; i
<p
.length(); i
++)
needs
.put(p
.charAt(i
), needs
.getOrDefault(p
.charAt(i
),0)+1);
int left
=0, right
=0;
while(right
<s
.length()){
char ch
= s
.charAt(right
);
if(needs
.containsKey(ch
)){
window
.put(ch
, window
.getOrDefault(ch
,0)+1);
if(window
.get(ch
).equals(needs
.get(ch
))){
count
++;
}
}
right
++;
while(count
==needs
.size()){
if(right
- left
== p
.length())
res
.add(left
);
char ch2
= s
.charAt(left
);
if(window
.containsKey(ch2
)){
window
.put(ch2
, window
.get(ch2
)-1);
if(window
.get(ch2
) < needs
.get(ch2
)){
count
--;
}
}
left
++;
}
}
return res
;
}
}
LeetCode最优解, 只用了一个哈希表, 本质是一样的
public class Solution {
public List
<Integer> findAnagrams(String s
, String t
) {
List
<Integer> result
= new LinkedList<>();
if(t
.length()> s
.length()) return result
;
Map
<Character, Integer> map
= new HashMap<>();
for(char c
: t
.toCharArray()){
map
.put(c
, map
.getOrDefault(c
, 0) + 1);
}
int counter
= map
.size();
int begin
= 0, end
= 0;
int head
= 0;
int len
= Integer
.MAX_VALUE
;
while(end
< s
.length()){
char c
= s
.charAt(end
);
if( map
.containsKey(c
) ){
map
.put(c
, map
.get(c
)-1);
if(map
.get(c
) == 0) counter
--;
}
end
++;
while(counter
== 0){
char tempc
= s
.charAt(begin
);
if(map
.containsKey(tempc
)){
map
.put(tempc
, map
.get(tempc
) + 1);
if(map
.get(tempc
) > 0){
counter
++;
}
}
if(end
-begin
== t
.length()){
result
.add(begin
);
}
begin
++;
}
}
return result
;
}
}
大佬的极致总结, 图末是他的公众号二维码
