leetcode30.串联所有单词的子串

利用词频字典进行单词统计+滑动窗口解决

class Solution {public List<Integer> findSubstring(String s, String[] words) {//1.边界判断s长度是否大于words中所有字符长度List<Integer> result = new ArrayList<>();int wordCount = words.length;int wordLen = words[0].length();int sLen = s.length();if (sLen < words.length * wordLen) {return result;}//2.定义一个词频字典，存储单词以及对应出现的次数Map<String, Integer> wordFreq = new HashMap<>();for (String word : words) {wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);}//3.按照不同的起始偏移量启动滑动窗口算法for (int i = 0; i < wordLen; i++) {//3.1定义滑动窗口中涵盖的单词数量以及滑动窗口中记录的词频int count = 0;Map<String, Integer> curFreq = new HashMap<>();//3.2滑动窗口算法实现for (int left = i, right = i; right + wordLen <= sLen; right += wordLen) {String curWord = s.substring(right, right + wordLen);//3.2.1当前单词在词频字典中，滑动窗口if (wordFreq.containsKey(curWord)) {curFreq.put(curWord, curFreq.getOrDefault(curWord, 0) + 1);count++;//3.2.1.1当前词频超过了词典中的词频就需要窗口左移，缩小窗口while (curFreq.get(curWord) > wordFreq.get(curWord)) {String leftWord = s.substring(left, left + wordLen);curFreq.put(leftWord, curFreq.get(leftWord) - 1);count--;left += wordLen;}//3.2.1.2当前窗口恰好涵盖了words中的所有单词，将当前窗口左边界加入结果集中，然后窗口左移if (count == wordCount) {result.add(left);String leftWord = s.substring(left, left + wordLen);curFreq.put(leftWord, curFreq.get(leftWord) - 1);count--;left += wordLen;}} else {//3.2.2当前单词不在次品字典中，直接清空一切curFreq.clear();count = 0;left = right + wordLen;}}}//4.返回结果return result;}
}