-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.java
More file actions
70 lines (66 loc) · 2.5 KB
/
Solution.java
File metadata and controls
70 lines (66 loc) · 2.5 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
package leetCode_30;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
/**
* @author dimdark
*/
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> results = new ArrayList<Integer>();
if (s == null || words == null || s.length() == 0 ||
words.length == 0 || words[0].length() == 0) {
return results;
}
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (String word : words) {
if (map.containsKey(word)) {
map.put(word, map.get(word) + 1);
} else {
map.put(word, 1);
}
}
int length = s.length();
int wordNumber = words.length;
int wordLength = words[0].length();
for (int i = 0; i < wordLength; ++i) {
int leftBound = i;
int count = 0;
HashMap<String, Integer> tmpMap = new HashMap<String, Integer>();
for (int j = i; j <= length - wordLength; j += wordLength) {
String word = s.substring(j, j + wordLength);
if (map.containsKey(word)) {
if (tmpMap.containsKey(word)) {
tmpMap.put(word, tmpMap.get(word) + 1);
} else {
tmpMap.put(word, 1);
}
if (tmpMap.get(word) <= map.get(word)) {
++count; // is valid word
} else {
while (tmpMap.get(word) > map.get(word)) {
String string = s.substring(leftBound, leftBound + wordLength);
if (tmpMap.get(string) <= map.get(string)) {
--count;
}
tmpMap.put(string, tmpMap.get(string) - 1);
leftBound += wordLength;
}
}
} else {
tmpMap.clear();
count = 0;
leftBound = j + wordLength;
}
if (count == wordNumber) {
results.add(leftBound);
String string = s.substring(leftBound, leftBound + wordLength);
tmpMap.put(string, tmpMap.get(string) - 1);
--count;
leftBound += wordLength;
}
}
}
return results;
}
}