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<String, Integer>来统计字符串的出现次数. 这里L数组中可能会出现两个相同的字符串.
public static ArrayList<Integer> findSubstring3(String S, String[] L) { ArrayList<Integer> results = new ArrayList<Integer>(); int len = L.length; if (len == 0) { results.add(0); return results; } int M = S.length(); int N = L[0].length(); Map<String, Integer> expected = new HashMap<String, Integer>(); Map<String, Integer> real = new HashMap<String, Integer>(); for (int j = 0; j < len; j++) { if (expected.get(L[j]) == null) { expected.put(L[j], 1); real.put(L[j], 0); } else { expected.put(L[j], expected.get(L[j]) + 1); } } // i的遍历范围是S的长度,减去L中所有String的长度和 for (int i = 0; i <= (M - N * len); i++) { int j = 0; for (; j < len;) { // 这里的j*N,j表示已经遇到的String的个数,N是L中每个String的长度 String tmp = S.substring(i + j * N, i + (j + 1) * N); if (expected.get(tmp) == null) { break; } else { real.put(tmp, real.get(tmp) + 1); // 下面的if 表示如果遇到String超过 expected了 就跳出 if (real.get(tmp) > expected.get(tmp)) { break; } j = j + 1; } } // j 表示在S中遇到L中String的个数,j == len 表示全部都遇到了 if (j == len) { results.add(i); } // 这里是将real清零 重新计算遇到的在L中的String for (int m = 0; m < len; m++) { real.put(L[m], 0); } } return results; }
Substring with Concatenation of All Words
原文:http://www.cnblogs.com/RazerLu/p/3552060.html