You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S:"barfoothefoobarman"
L:["foo", "bar"]You should return the indices:
[0,9].
(order does not matter).
使用map来存储，并进行判断。public List<Integer> findSubstring(String S, String[] L) { List<Integer> list = new ArrayList<Integer>(); int arrLen = L.length; int strLen = L[0].length(); Map<String, Integer> map = new HashMap<String, Integer>(); for (int i = 0; i < arrLen; i++) { if (map.get(L[i]) == null) { map.put(L[i], 1); } else { map.put(L[i], map.get(L[i]) + 1); } } Map<String, Integer> tempMap = new HashMap<String, Integer>(); for (int i = 0; i < S.length() - arrLen * strLen + 1; i++) { tempMap.clear(); boolean flag = true; for (int j = 0; j < arrLen && flag; j++) { String str = S.substring(i + j * strLen, i + (j + 1 )* strLen); if (map.containsKey(str)) { tempMap.put(str, tempMap.get(str) == null ? 1 : tempMap.get(str) + 1); if (tempMap.get(str) > map.get(str)) { flag = false; } } else { flag = false; } } if (flag) { list.add(i); } } return list; }
Substring with Concatenation of All Words,布布扣,bubuko.com
Substring with Concatenation of All Words
原文：http://blog.csdn.net/u010378705/article/details/34838377