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).
讲道理，这题目，真的是……题意好理解，找字符串中的放一起的子串，标记位置。超时了好多次，声明一下string s 改为S，words改为L
代码如下：
public class Solution { public List<Integer> findSubstring(String S, String[] L) { List<Integer> ret = new ArrayList<Integer>(); int slen = S.length(), llen = L.length; if (slen <= 0 || llen <= 0) return ret; int wlen = L[0].length(); HashMap<String, Integer> words = new HashMap<String, Integer>(); for (String str : L) { if (words.containsKey(str)) { words.put(str, words.get(str) + 1); } else { words.put(str, 1); } } for (int i = 0; i < wlen; ++i) { int left = i, count = 0; HashMap<String, Integer> tmap = new HashMap<String, Integer>(); for (int j = i; j <= slen - wlen; j += wlen) { String str = S.substring(j, j + wlen); if (words.containsKey(str)) { if (tmap.containsKey(str)) { tmap.put(str, tmap.get(str) + 1); } else { tmap.put(str, 1); } if (tmap.get(str) <= words.get(str)) { count++; } else { while (tmap.get(str) > words.get(str)) { String tmps = S.substring(left, left + wlen); tmap.put(tmps, tmap.get(tmps) - 1); if (tmap.get(tmps) < words.get(tmps)) { count--; } left += wlen; } } if (count == llen) { ret.add(left); String tmps = S.substring(left, left + wlen); tmap.put(tmps, tmap.get(tmps) - 1); count--; left += wlen; } } else { tmap.clear(); count = 0; left = j + wlen; } } } return ret; }