LeetCode 030 - Substring with Concatenation of All Words - 题解/Solution

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

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
/**
* You are given a string, s, and a list of words, words, that are all of the
* same length. Find all starting indices of substring(s) in s that is a
* concatenation of each word in words exactly once and without any intervening
* characters.
*
* For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]
*
* You should return the indices: [0,9]. (order does not matter).
*
* @author dongyuxi
*
*/
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> list = new ArrayList<Integer>();
if (null == s || 0 == s.length() || null == words || 0 == words.length) {
return list;
}
Map<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 wordsNumber = words.length;
int wordLength = words[0].length();
for (int i = 0; i <= s.length() - wordsNumber * wordLength; i++) {
Map<String, Integer> tempMap = new HashMap<String, Integer>(map);
for (int j = i; j <= i + (wordsNumber - 1) * wordLength; j += wordLength) {
String subword = s.substring(j, j + wordLength);
if (tempMap.containsKey(subword)) {
if (tempMap.get(subword) == 1) {
tempMap.remove(subword);
} else {
tempMap.put(subword, tempMap.get(subword) - 1);
}
} else {
break;
}
}
if (0 == tempMap.size()) {
list.add(i);
}
}
return list;
}
}


支付宝 微信
文章目录