30 Substring with Concatenation of All Words
题目：
给出一串字符串 s=“foobarbarthefoobarman”
和一个字典words = {"foo","bar","bar"}
- 字典的特点：
所有单词的长度一致，单词可以重复 - 要求：
找出s里面包含的特定字符串的起始位置，这个特定字符串，指的是满足以下条件：
由字典里面的所有单词拼接起来的
如words = {"foo","bar","bar"}， 那么 “foobarbar” 或者 “barfoobar” ...就是符合要求的子串 - 注意事项：
ｓ的默认长度是单词的倍数（思考一下，如果不是，怎么办？）
思考
- 怎么确定不仅匹配单词，而且匹配单词里面的数目呢？ 【可以用HashMap来记录】
- 词窗怎么选择？ （这道题很容易就联想到直接套用leetcode 187 的那种长词窗的方法）
【词窗会不会太长？会超时吗？里面的单词有没有规律？可不可以编码？】 - 词窗怎么移动？ 从哪里开始，到哪里结束？ 能不能涵盖所有的情况？
思路
- 这道题如果把词窗大小设置为 window_size = words.length * words[0].length(),
有以下缺点：
1. 词窗太长
2. 如果对里面的单词，每words[0].lenght()个进行编码，比较繁琐
-
新思路：“隐”词窗 和 “显”词窗
** 隐词窗 ** = words.length * words[0].length()，
但是我们只用一个 index来记录这个词窗的起点
显词窗 = 单个单词的长度， ** window_size = words[0].length()
- 怎么样才能遍历所有情况？
- 如何移动词窗？有没有trick可以节省运算？
- 如何记录单词出现次数？ 【用辅助的HashMap来记录单词以及词频，用count来记录匹配个数】
- 要考虑到什么特殊情况？ 【如果某一个单词出现的次数超过了字典中对应单词的词频，怎么处理】
解决方法
- 词窗大小为一个单词的大小，从左往右移动，每次移动的间隔是wordlen
**范围是 ： **
for(int i=0; i<=s.length()-word_len; i++) // 记得是 <= 这个地方很重要，不然会漏了所有可能的遍历情况
{
for(int j=i; j<=s.length()-word_len; j++) // 记得是 <=
{
int left = i; // 用来记录符合要求的 “隐” 词窗的起点
String currentStr = s.substring(j, j+wordlen);
...
}
}
每次对currentStr进行如下检测：
如果词窗内的单词在词典内
（1）如果helper里面没有记录过这个单词？ --> helper.put(currentStr, 1) ,同时 count++
（2）如果helper里面有这个单词 --> helper.put(currentStr, helper.get(currentStr)+1)
记录了之后，超出map.get(currentStr)吗？超出了从隐形词窗的起点开始，不断更新隐形词窗的边界，直到 helper.get(currentStr)<= map.get(currentStr),
过程中要不断更新 helper 和 count
（3）找到了一个符合题目要求的解之后，要怎么移动“隐”词窗的边界？
既然知道这是一个解，说明里面的都是符合条件的单词，我们只需要把隐词窗的边界移动一个wordlen的长度，去掉隐词窗最前面的那个word，更新helper和count即可。如果词窗内的单词不在词典内那么前面所匹配到的一切都无效了，因为题目要求的是连续的拼接。
具体代码：见github
参考： http://yuanhsh.iteye.com/blog/2187543
