LeetCode 30与所有单词相关联的字串

给定一个字符串 s 和一些长度相同的单词 words。在 s 中找出可以恰好串联 words 中所有单词的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1:

输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出: [0,9]

解释: 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

输入:
s = "wordgoodstudentgoodword",
words = ["word","student"]
输出: []

解法

这道题有一个很关键的条件长度相同的单词,单词长度一致这个题可以退化为单词长度为1来考虑。问题变成：给定一个字符串，寻找由字母集words组成的字串。这种字符串问题就可以考虑使用一个滑窗来解决，扫描源字符串，如果新增单词是单词集words中的单词，并且该单词未在滑窗中出现滑窗增涨（滑窗right增加），否则滑窗缩小（滑窗left增加）。当滑窗满足需求时，记录滑窗左侧（left）的位置,继续扫描，直至无法在生成满足需求的滑窗为止。

代码

class Solution {

   public List<Integer> findSubstring(String s, String[] words) {
       List<Integer> result = new ArrayList<>();
       if (s == null || s.length() == 0 || words == null || words.length == 0) {
           return result;
       }
       Map<String, Integer> wordsCount = generateCount(words);
       int length = words[0].length();

       for (int i = 0; i < length; ++i) {
           Map<String, Integer> window = new HashMap<>();
           int left = i;
           int right = i;
           while (right <= s.length() - length && left <= s.length() - length * words.length) {
               String sub = s.substring(right, right + length);
               incr(window, sub);
               if (!wordsCount.containsKey(sub)) {
                   window.clear();
                   right += length;
                   left = right;
                   continue;
               }
               while (window.get(sub) > wordsCount.get(sub)) {
                   decr(window, s.substring(left, left + length));
                   left += length;
               }
               right += length;
               if (right - left == length * words.length) {
                   result.add(left);
               }
           }
       }
       return result;
   }

   private Map<String, Integer> generateCount(String[] words) {
       Map<String, Integer> wordsCount = new HashMap<>();
       for (String word : words) {
           incr(wordsCount, word);
       }
       return wordsCount;
   }

   private void incr(Map<String, Integer> map, String key) {
       if (map.containsKey(key)) {
           map.put(key, map.get(key) + 1);
       } else {
           map.put(key, 1);
       }
   }

   private void decr(Map<String, Integer> map, String key) {
       if (map.containsKey(key)) {
           Integer value = map.get(key);
           if (value <= 1) {
               map.remove(key);
           } else {
               map.put(key, value - 1);
           }
       }
   }
}