算法-滑动窗口-串联所有单词的子串

算法-滑动窗口-串联所有单词的子串

1 题目概述

1.1 题目出处

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

1.2 题目描述

2 滑动窗口+Hash表

2.1 解题思路

1. 构建一个大小为串联子串的总长的滑动窗口
2. 为每个words中的子串创建一个hash表, <子串值，子串出现次数>
3. 记录每次开始位置，从左往右遍历字符串s，每次截取words[0]长度的子串，和2中hash表对比，如果没有或者使用次数超限，就表示该组合无法构成，退出该次检测；否则继续检测，直到构成的串联子串长度满足要求或者已检测长度超限。构建成功时，记录下起始序号
4. 一轮检测完成后，窗口向右滑动1个长度，继续下一轮检测

2.2 代码

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> resultList = new ArrayList<>();int windowSize = words[0].length();if (windowSize > s.length()) {return resultList;}int strLength = windowSize * words.length;if (strLength > s.length()){return resultList;}Map<String, Integer> wordMap = new HashMap<>();for (int i = 0; i < words.length; i++) {Integer subKeyTimes = wordMap.get(words[i]);if (null == subKeyTimes) {subKeyTimes = 0;} wordMap.put(words[i], subKeyTimes + 1);}for (int i = 0; i <= s.length() - strLength; i++) {int result = getStart(s, words, strLength, windowSize, i, wordMap);if (result != -1) {resultList.add(result);}}return resultList;}private int getStart(String s, String[] words, int strLength, int windowSize, int first, Map<String, Integer> wordMap) {int start = -1;int length = 0;Map<String, Integer> useMap = new HashMap();for (int i = first; i < s.length() && length < strLength && i < first + strLength; i += windowSize) {String sub = s.substring(i, i + windowSize);Integer subKeyTimes = wordMap.get(sub);if (null == subKeyTimes) {return -1;}Integer useTimes = useMap.get(sub);if (null == useTimes) {useTimes = 1; } else {useTimes += 1;}if (useTimes > subKeyTimes) {return -1;}useMap.put(sub, useTimes);length += windowSize;if (start == -1) {start = i;}}if (length == strLength) {return start;}return -1;}
}

2.3 时间复杂度

s.length=n，words.length=m ，时间复杂度O(n*m)

2.4 空间复杂度

O(m)

3 回溯法+交换字符串

3.1 解题思路

3.2 代码

3.3 时间复杂度

3.4 空间复杂度

O(N)