!!Substring with Concatenation of All Words
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).
Solution
- Brute + HashMap.
- Sliding Window + HashMap. from Sun Mian.
Code
public class Solution {
public List<Integer> findSubstring(String S, String[] L) {
List<Integer> res = new ArrayList<Integer>();
if(L.length==0 || S==null || S.length()==0) return res;
int M = S.length(), N = L.length;
int K = L[0].length();
HashMap<String, Integer> need = new HashMap<String, Integer>();
for(String str: L) {
if(need.containsKey(str)) {
need.put(str, need.get(str)+1);
} else {
need.put(str, 1);
}
}
for (int i = 0; i <= M - N*K; ++i) {
HashMap<String, Integer> found = new HashMap<String, Integer>();
int j = 0;
for (j = 0; j < N; ++j) {
String s = S.substring(i + j * K, i + (j+1) * K);
if (need.containsKey(s) == false) break;
if (found.containsKey(s) == true) {
if (need.get(s) <= found.get(s)) break;
found.put(s, found.get(s)+1);
} else found.put(s, 1);
}
if (j == N) res.add(i);
}
return res;
}
public List<Integer> findSubstring_2(String S, String[] L) {
List<Integer> list = new ArrayList<>();
Map<String, Integer> need = new HashMap<>();
for(String str: L) {
if(need.containsKey(str)) {
need.put(str, need.get(str)+1);
} else {
need.put(str, 1);
}
}
int n = L[0].length(), m = L.length;
for (int i = 0; i < n; ++i) {
Map<String, Integer> find = new HashMap<>();
for (int start = i, end = i, count = 0; end + n <= S.length(); end += n) {
String str = S.substring(end, end + n);
if (need.get(str) == null) {
start = end + n;
find.clear();
count = 0;
continue;
}
while (find.get(str) != null && find.get(str) >= need.get(str)) {
String subStart = S.substring(start, start + n);
find.put(subStart, find.get(subStart) - 1);
start += n;
--count;
}
find.put(str, (find.get(str) == null ? 0 : find.get(str)) + 1);
++count;
if (count != m) continue;
list.add(start);
}
}
return list;
}
}