本文的参考文献为：【1】Code_Ganker博客：【2】哎-哭泣的鱼的博客：本文的写作目的有两个：一、自私的为自己做一个备份；二、在观看了上两位大神的博客之后，发现代码没有注释，所以斗胆加入注释，使得更易于阅读。为了避免重复造车，大部分使用【2】的内容，在需要添加的地方，加入个人的解释。姑且算是原创吧，不要见怪。Substring with Concatenation of All WordsYou 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).【解题思路】 我看了好几天都没明白题目到底是什么意思，英文描述和汉语描述起来还是有很大差异。事实上求解的是S中包含L中所有单词的index，换句话说，假设L中单词长度为wordLen，总长为wordLen*len，从index到距离为总长的这一段包含L中所有的单词。例如题目中的0到5，9到14包含L中的所有单词。有两种思路解决这个问题。1、暴力搜索(Java AC的代码是1044ms) 【建议先看2，有注释】针对S中每个字符开始搜索一次长度为wordLen*len的字符串，是否包含L中的所有单词。这个很好统计，Map就可以直接搞定。思路很好想，同时也很费时。
Java AC
public class Solution {public ArrayList<Integer> findSubstring(String S, String[] L) {ArrayList<Integer> list = new ArrayList<Integer>();int len = L.length;if (len == 0) {return list;}int wordLen = L[0].length();Map<String, Integer> wordsMap = new HashMap<String, Integer>();for (int i = 0; i < len; i++) {int num = 1;if (wordsMap.get(L[i]) != null) {num += wordsMap.get(L[i]);}wordsMap.put(L[i], num);}int slen = S.length();int max = slen – len * wordLen + 1;for (int i = 0; i < max; i++) {Map<String, Integer> numMap = new HashMap<String, Integer>();int j = 0;for (; j < len; j++) {int start = i + j * wordLen;int end = start + wordLen;String tempStr = S.substring(start, end);if (!wordsMap.containsKey(tempStr)) {break;}int num = 1;if (numMap.get(tempStr) != null) {num += numMap.get(tempStr);}if (num > wordsMap.get(tempStr)) {break;}numMap.put(tempStr, num);}if (j == len) {list.add(i);}}return list;}}2、最小滑动窗口(Java AC的代码是448ms)
因为L中所有单词的长度是一样的，这样根据wordLen，可以将S分为wordLen组，实际意思是这样的。
以题目中barfoothefoobarman举例，L中单词长度为3，可以分为
bar|foo|the|foo|bar|man
ba|rfo|oth|efo|oba|rma|n
b|arf|oot|hef|oob|arm|an
这样，针对每个分组，可以利用最小滑动窗口的思想，快速的判断是否包含需要的字符串。
直观上来看，1和2好像都是需要从每个字符开始搜索，实际上，2利用两个指针去在S中寻找满足条件的字符串，并且是每次+wordLen，而且不会重复的去统计，节省了很多时间。
【注】作者上述优点解释不清，其实代码1也可以理解为一个滑动窗口的程序，只不过每次窗口向后移动1步，而代码而是移动wordlen步，但是代码二最外层还有一个for循环，循环次数为wordlen，所以这么看，这两种其实没有本质的区别。 那么为什么代码2会比代码1的效率高？有两点：
一、if (!wordsMap.containsKey(tempStr))此代码，如果一旦判定为真，即字典中不包含次Str，那么窗口将会向后移动wordlen*n，n>=1，当n>1时，使性能得到很大的提升；而在代码1中，相同的判断，仅仅是将窗口向后移动1步（相当于使代码2中上述的n永远等于1的效率）。
二、其实关键点是在一下代码中加入了/**********/标记之后的while循环，如果在代码一中，一旦出现了不匹配，只能清除匹配结果，再将窗口向后移动1步。而代码而，其中的numMap.get(tempStr) > wordsMap.get(tempStr)判断未真，即表示窗口中的tempStr字符串的个数，比字典中的大，也就是表明，这个窗口将不会匹配成功，所以立马将窗口向后移动只此窗口第一次出现tempStr字符串的位置之后（若每次tempStr都是在窗口的首位置，那么性能和代码1将相同，若不在首位置，那么移动的就是wordlen*n，n>1这样将会使得代码的性能得到很大的提升）。
Java AC
import java.util.HashMap;import java.util.Map;import java.util.ArrayList;public class SubstringWithConcatenationOfAllWords { public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> list = new ArrayList<Integer>(); int len = L.length; if (len == 0) { return list; } int wordLen = L[0].length(); Map<String, Integer> wordsMap = new HashMap<String, Integer>(); for (int i = 0; i < len; i++) { //将字典放入Map中 if (wordsMap.containsKey(L[i])) { //有重复的词，进行个数增加处理 wordsMap.put(L[i],wordsMap.get(L[i])+1); } else wordsMap.put(L[i], 1); } int slen = S.length(); int max = slen – wordLen + 1; for (int i = 0; i < wordLen; i++) { //bar|foo|the|foo|bar|man 三种移位方式 //ba|rfo|oth|efo|oba|rma|n //b|arf|oot|hef|oob|arm|an Map<String, Integer> numMap = new HashMap<String, Integer>(); //建立S的Map int count = 0; //用来统计总体匹配个数 int start = i; for (int end = start; end < max; end += wordLen) { //在某一种移位方式下，进行遍历 String tempStr = S.substring(end, end + wordLen); //读取子字符串 if (!wordsMap.containsKey(tempStr)) { //若没有匹配，直接从清零前期的匹配，从这个词之后开始 numMap.clear(); count = 0; start = end + wordLen; continue; } if (numMap.containsKey(tempStr)) { //已经包含，，则进行个数的增加处理 numMap.put(tempStr,numMap.get(tempStr)+1); } else numMap.put(tempStr, 1); if (numMap.get(tempStr) <= wordsMap.get(tempStr)) { //判断key=tempStr S中的个数和字典中的个数的大小 count++; } else { /**********************************************/ while (numMap.get(tempStr) > wordsMap.get(tempStr)) { //若S中的大，则从tempStr之后开始匹配 tempStr = S.substring(start, start + wordLen); numMap.put(tempStr, numMap.get(tempStr) – 1); if (numMap.get(tempStr) < wordsMap.get(tempStr)) { //之前的匹配结果统计取消 count–; } start += wordLen; } } if (count == len) { //若个数相同，说明完全匹配 list.add(start); tempStr = S.substring(start, start + wordLen); numMap.put(tempStr, numMap.get(tempStr) – 1);//去除最前面的一个word继续向后匹配 count–; start += wordLen; } } } return list; } public static void main(String[] args) { }}
因害怕失败而不敢放手一搏，永远不会成功
