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()

1. 怎么样才能遍历所有情况？
2. 如何移动词窗？有没有trick可以节省运算？
3. 如何记录单词出现次数？ 【用辅助的HashMap来记录单词以及词频，用count来记录匹配个数】
4. 要考虑到什么特殊情况？ 【如果某一个单词出现的次数超过了字典中对应单词的词频，怎么处理】

解决方法

• 词窗大小为一个单词的大小，从左往右移动，每次移动的间隔是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. 如果词窗内的单词在词典内
   （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即可。

2. 如果词窗内的单词不在词典内那么前面所匹配到的一切都无效了，因为题目要求的是连续的拼接。

---

具体代码：见github
参考： http://yuanhsh.iteye.com/blog/2187543