友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
438. Find All Anagrams in a String
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".解题分析
使用滑动窗口来"圈定"字符串！
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/**
* Runtime: 18 ms, faster than 51.95% of Java online submissions for Find All Anagrams in a String.
* Memory Usage: 42.6 MB, less than 6.00% of Java online submissions for Find All Anagrams in a String.
*
* Copy from: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/[滑动窗口通用思想解决子串问题 - 找到字符串中所有字母异位词 - 力扣（LeetCode）]
*/
public List<Integer> findAnagrams(String s, String p) {
if (Objects.isNull(s) || s.length() == 0
|| Objects.isNull(p) || p.length() == 0
|| s.length() < p.length()) {
return Collections.emptyList();
}
Map<Character, Integer> needs = new HashMap<>(p.length());
for (char c : p.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
Map<Character, Integer> windows = new HashMap<>(p.length());
int match = 0;
List<Integer> result = new ArrayList<>();
while (right < s.length()) {
char rChar = s.charAt(right);
if (needs.containsKey(rChar)) {
int rCount = windows.getOrDefault(rChar, 0) + 1;
windows.put(rChar, rCount);
if (rCount == needs.get(rChar)) {
match++;
}
}
right++;
while (match == needs.size()) {
if (right - left == p.length()) {
result.add(left);
}
char lChar = s.charAt(left);
if (needs.containsKey(lChar)) {
Integer lCount = windows.get(lChar) - 1;
windows.put(lChar, lCount);
if (lCount < needs.get(lChar)) {
match--;
}
}
left++;
}
}
return result;
}
/**
* Time Limit Exceeded
*/
public List<Integer> findAnagramsSort(String s, String p) {
if (Objects.isNull(s) || s.length() == 0
|| Objects.isNull(p) || p.length() == 0
|| s.length() < p.length()) {
return Collections.emptyList();
}
char[] chars = p.toCharArray();
Arrays.sort(chars);
List<Integer> result = new ArrayList<>();
for (int i = 0; i <= s.length() - p.length(); i++) {
char[] subchars = s.substring(i, i + p.length()).toCharArray();
Arrays.sort(subchars);
if (Arrays.equals(chars, subchars)) {
result.add(i);
}
}
return result;
}
/**
* Time Limit Exceeded
*/
public List<Integer> findAnagramsPermutations(String s, String p) {
if (Objects.isNull(s) || s.length() == 0
|| Objects.isNull(p) || p.length() == 0
|| s.length() < p.length()) {
return Collections.emptyList();
}
ArrayList<Character> chars = new ArrayList<>();
for (char c : p.toCharArray()) {
chars.add(c);
}
HashSet<String> anagrams = new HashSet<>();
buildAnagrams(chars, anagrams, 0);
List<Integer> result = new ArrayList<>();
for (int i = 0; i <= s.length() - p.length(); i++) {
String substring = s.substring(i, i + p.length());
if (anagrams.contains(substring)) {
result.add(i);
}
}
return result;
}
private void buildAnagrams(List<Character> chars, Set<String> result, int index) {
if (index == chars.size()) {
StringBuilder builder = new StringBuilder();
for (Character aChar : chars) {
builder.append(aChar);
}
result.add(builder.toString());
return;
}
for (int i = index; i < chars.size(); i++) {
Collections.swap(chars, i, index);
buildAnagrams(chars, result, index + 1);
Collections.swap(chars, i, index);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-02 17:52:50
*/
public List<Integer> findAnagrams(String s, String p) {
if (s == null || s.isEmpty()
|| p == null || p.isEmpty()
|| s.length() < p.length()) {
return Collections.emptyList();
}
Map<Character, Integer> need = new HashMap<>();
for (char c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int valid = 0;
List<Integer> result = new ArrayList<>();
while (right < s.length()) {
char rc = s.charAt(right);
right++;
if (need.containsKey(rc)) {
window.put(rc, window.getOrDefault(rc, 0) + 1);
if (window.get(rc).equals(need.get(rc))) {
valid++;
}
}
while (valid == need.size()) {
if (right - left == p.length()) {
result.add(left);
}
char lc = s.charAt(left);
if (need.containsKey(lc)) {
window.put(lc, window.get(lc) - 1);
if (window.get(lc) < need.get(lc)) {
valid--;
}
}
left++;
}
}
return result;
}