0x030 串联所有单词的子串

https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

思路：

1、由于单词的长度固定，因此可以采用按词匹配的方式

2、使用滑动窗口的思路，边移入，边移出

• 若出现单词不匹配的情况，则调整起始位置start与匹配字典cur_dict
• 全单词匹配的情况下，即matched == word_cnt，将起始位置加入结果集

public static List<Integer> findSubstring(String s, String[] words) { int n = s.length(); LinkedList<Integer> ans = new LinkedList<>(); if (n == 0) { return ans; } int word_cnt = words.length; int m = words[0].length(); HashMap<String, Integer> word_dict = new HashMap<>(); for (String word : words) { word_dict.put(word, word_dict.getOrDefault(word, 0) 1); } for (int i = 0; i < m; i ) { // 遍历起始 HashMap<String, Integer> cur_dict = new HashMap<>(); int start = i; int matched = 0; for (int r = start; r < n && r m <= n; r = m) { // 按词遍历 String word = s.substring(r, r m); // 未匹配 if (!word_dict.containsKey(word)) { start = r m; matched = 0; cur_dict = new HashMap<>(); continue; } // 移入 cur_dict.put(word, cur_dict.getOrDefault(word, 0) 1); matched ; // 移出 while (cur_dict.get(word) > word_dict.get(word)) { String next_word = s.substring(start, start m); cur_dict.put(next_word, cur_dict.get(next_word) - 1); matched--; start = m; } // 匹配成功 if (matched == word_cnt) { ans.add(start); } } } return ans; }