-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathLeetCode_00030.java
More file actions
106 lines (102 loc) · 3.85 KB
/
LeetCode_00030.java
File metadata and controls
106 lines (102 loc) · 3.85 KB
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
package com.github.jerring.leetcode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class LeetCode_00030 {
// public List<Integer> findSubstring(String s, String[] words) {
// List<Integer> res = new ArrayList<>();
// if (words.length == 0 || s.length() < words.length * words[0].length()) {
// return res;
// }
// Map<String, Integer> src = new HashMap<>();
// for (String word : words) {
// src.put(word, src.getOrDefault(word, 0) + 1);
// }
// int len = words[0].length();
// int window = words.length * len;
// // 分别从 [0, len) 开始寻找
// for (int i = 0; i < len; ++i) {
// // 复制一份，避免上次循环对这次的干扰
// Map<String, Integer> map = new HashMap<>(src);
// // 初始化 size 为当前单词数量
// int size = words.length;
// // 窗口 [l, r) 从本次起始位置 i 开始
// int l = i, r = i;
// while (r + len <= s.length()) {
// String sub = s.substring(r, r + len);
// r += len;
// if (map.containsKey(sub)) {
// // 对应计数减一
// map.put(sub, map.get(sub) - 1);
// // 在有效范围内更新 size
// if (map.get(sub) >= 0) {
// --size;
// }
// }
// while (size == 0) {
// if (r - l == window) {
// res.add(l);
// }
// sub = s.substring(l, l + len);
// l += len;
// if (map.containsKey(sub)) {
// // 对应计数加一
// map.put(sub, map.get(sub) + 1);
// // 在有效范围内更新 size
// if (map.get(sub) > 0) {
// ++size;
// }
// }
// }
// }
// }
// return res;
// }
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if (words.length == 0 || s.length() < words.length * words[0].length()) {
return res;
}
Map<String, Integer> src = new HashMap<>();
for (String word : words) {
src.put(word, src.getOrDefault(word, 0) + 1);
}
int len = words[0].length();
int window = words.length * len;
for (int i = 0; i < len; ++i) {
// 构建一个空的 HashMap
Map<String, Integer> map = new HashMap<>();
int size = words.length;
int l = i, r = i;
while (r + len <= s.length()) {
String sub = s.substring(r, r + len);
r += len;
if (src.containsKey(sub)) {
// 对应计数加一
map.put(sub, map.getOrDefault(sub, 0) + 1);
// 在有效范围内更新 size
if (map.get(sub) <= src.get(sub)) {
--size;
}
}
while (size == 0) {
if (r - l == window) {
res.add(l);
}
sub = s.substring(l, l + len);
l += len;
if (src.containsKey(sub)) {
// 对应计数减一
map.put(sub, map.get(sub) - 1);
// 在有效范围内更新 size
if (map.get(sub) < src.get(sub)) {
++size;
}
}
}
}
}
return res;
}
}