Repository navigation
Expand file tree
/
Copy pathSolution.java
More file actions
112 lines (108 loc) 路 4.33 KB
/
Copy pathSolution.java
File metadata and controls
112 lines (108 loc) 路 4.33 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
107
108
109
110
111
112
package _030;
import java.util.*;
/**
* <pre>
* author: Blankj
* blog : http://blankj.com
* time : 2018/02/01
* desc :
* </pre>
*/
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int wordsSize = words.length, wordLen = words[0].length(), end = s.length() - wordsSize * wordLen;
if (end < 0) return Collections.emptyList();
Map<String, Integer> countMap = new HashMap<>();
for (String word : words) {
countMap.put(word, countMap.getOrDefault(word, 0) + 1);
}
List<Integer> res = new ArrayList<>();
Set<Integer> ignores = new HashSet<>();
for (int i = 0; i <= end; ++i) {
if (ignores.contains(i)) continue;
Map<String, Integer> findMap = new HashMap<>();
int st = i, count = 0;
List<Integer> ignore = new ArrayList<>();
for (int j = 0; ; ++j) {
int cur = i + j * wordLen;
if (cur + wordLen > s.length()) break;
String word = s.substring(cur, cur + wordLen);
if (countMap.containsKey(word)) {
findMap.put(word, findMap.getOrDefault(word, 0) + 1);
++count;
while (findMap.get(word) > countMap.get(word)) {
ignore.add(st);
String tmp = s.substring(st, st += wordLen);
findMap.put(tmp, findMap.get(tmp) - 1);
--count;
}
if (count == wordsSize) {
ignore.add(st);
res.add(st);
String tmp = s.substring(st, st += wordLen);
findMap.put(tmp, findMap.get(tmp) - 1);
--count;
}
} else {
for (int k = i; k <= cur; k += wordLen) {
ignore.add(k);
}
break;
}
}
ignores.addAll(ignore);
}
return res;
}
// public List<Integer> findSubstring(String S, String[] L) {
// List<Integer> res = new LinkedList<>();
// int N = S.length();
// int M = L.length; // *** length
// int wl = L[0].length();
// Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();
// for (String s : L) {
// if (map.containsKey(s)) map.put(s, map.get(s) + 1);
// else map.put(s, 1);
// }
// String str = null, tmp = null;
// for (int i = 0; i < wl; i++) {
// int count = 0; // remark: reset count
// int start = i;
// for (int r = i; r + wl <= N; r += wl) {
// str = S.substring(r, r + wl);
// if (map.containsKey(str)) {
// if (curMap.containsKey(str)) curMap.put(str, curMap.get(str) + 1);
// else curMap.put(str, 1);
//
// if (curMap.get(str) <= map.get(str)) count++;
// if (count == M) {
// res.add(start);
// tmp = S.substring(start, start + wl);
// curMap.put(tmp, curMap.get(tmp) - 1);
// start += wl;
// count--;
// }
// while (curMap.get(str) > map.get(str)) {
// tmp = S.substring(start, start + wl);
// curMap.put(tmp, curMap.get(tmp) - 1);
// start += wl;
// if (curMap.get(tmp) < map.get(tmp)) count--;
//
// }
// } else {
// curMap.clear();
// count = 0;
// start = r + wl;
// }
// }
// curMap.clear();
// }
// return res;
// }
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "good"}));
System.out.println(solution.findSubstring("barfoothefoobarman", new String[]{"foo", "bar"}));
System.out.println(solution.findSubstring("barfoofoobarthefoobarman", new String[]{"bar", "foo", "the"}));
}
}