【Day 23 】2022-11-23 - 30. 串联所有单词的子串

[azl397985856]

30. 串联所有单词的子串

入选理由

暂无

题目地址

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

前置知识

• 哈希表
• 双指针

  题目描述

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

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

示例 1： 输入： s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。 示例 2：

输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[]

[snmyj]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int totalLen = s.length();
        int len = words[0].length();
        int n = words.length;
        if (n*totalLen == 0){
            return result;
        }
        HashMap<String,Integer> wordMap = new HashMap<>();
        for (String word:words) {
            int value = wordMap.getOrDefault(word, 0);
            wordMap.put(word,value+1);
        }
        
        for (int i = 0; i <totalLen-n*len+1; i++) {
          
            Map<String,Integer> hasWords = new HashMap<>();
            int num = 0;
            while (num < n){
                String currWord = s.substring(i+num*len,i+(num+1)*len);
                if (wordMap.containsKey(currWord)){
                    int value = hasWords.getOrDefault(currWord,0);
                    hasWords.put(currWord,value+1);
                    if (wordMap.get(currWord) < hasWords.get(currWord)){
                        break;
                    }
                }else {
                    break;
                }
                num++;
            }
            if (num == n){
                result.add(i);
            }
        }
        return result;
    }
}

[zywang0]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int totalLen = s.length();
        int len = words[0].length();
        int n = words.length;
        if (n*totalLen == 0){
            return result;
        }
        HashMap<String,Integer> wordMap = new HashMap<>();
        for (String word:words) {
            int value = wordMap.getOrDefault(word, 0);
            wordMap.put(word,value+1);
        }
        
        for (int i = 0; i <totalLen-n*len+1; i++) {
          
            Map<String,Integer> hasWords = new HashMap<>();
            int num = 0;
            while (num < n){
                String currWord = s.substring(i+num*len,i+(num+1)*len);
                if (wordMap.containsKey(currWord)){
                    int value = hasWords.getOrDefault(currWord,0);
                    hasWords.put(currWord,value+1);
                    if (wordMap.get(currWord) < hasWords.get(currWord)){
                        break;
                    }
                }else {
                    break;
                }
                num++;
            }
            if (num == n){
                result.add(i);
            }
        }
        return result;
    }
}

[zhiyuanpeng]

class Solution:
    def helper(self, s, start, words, w_len, s_len, golden):
        ans = []
        if len(s) < s_len:
            return ans
        l, r = 0, 0
        target = collections.defaultdict(int)
        for r in range(0, s_len, w_len):
            target[s[r: w_len+r]] += 1
        if target == golden:
            ans.append(l+start)

        if s_len > len(s) - w_len:
            return ans

        for r in range(s_len, len(s), w_len):
            target[s[r: r+w_len]] += 1
            target[s[l: l+w_len]] -= 1
            if target[s[l: l+w_len]] == 0:
                del target[s[l: l+w_len]]
            l += w_len
            if target == golden:
                ans.append(l+start)
        return ans

    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        w_len = len(words[0])
        s_len = len(words)*w_len
        ans = []
        target = collections.Counter(words)
        if len(s) < s_len:
            return ans
        else:
            for i in range(w_len):
                ans += self.helper(s[i:], i, words, w_len, s_len, target)
            return ans

time O(N) space O(N)

[StaringWhere]

思路

用 word.length - 1 个 sliding window，因为我们的步长是 word,length。用hash table记录下单次出现的位置，通过与start位置对比，就可以知道是否在这个substring里出现过。用queue作为hash table里的value来存储位置，解决重复的word的问题，因为是从前向后遍历，因此queue里的位置是自动排序的，每次对比只需要对比queue.front()。

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        unordered_map<string, unsigned> count;
        for (auto& word : words) {
            count[word]++;
        }
        unsigned length = words[0].length();
        for (unsigned i = 0; i < length; i++) {
            unordered_map<string, queue<unsigned>> pos;
            int start = i;
            for (unsigned j = i; j < s.length() - length + 1; j += length) {
                string sub = s.substr(j, length);
                if (count.count(sub)) {
                    if (pos[sub].size() == count[sub] && pos[sub].front() >= start) {
                        start = pos[sub].front() + length;
                    }
                    if (pos[sub].size() == count[sub]) {
                        pos[sub].pop();
                    }
                    pos[sub].push(j);
                }
                else {
                    start = j + length;
                }
                if (j + length - start == length * words.size()) {
                    res.push_back(start);
                    start += length;
                }
            }
        };
        return res;
    }
};

复杂度分析

时间 O(words.size() + s.length() * word.length())
空间 O(words.size() + word.length())

[mayloveless]

思路

把word存一个map，记录出现次数，遍历s，每次遍历，当作以当前字符为开头的，是否满足条件：每隔一个word长度判断是否存在map中且数量符合。

var findSubstring = function(s, words) {
     if(!s || !words.length) return [];
    const wordsCount = words.length;
    const oneLen = words[0].length
    const len = wordsCount * oneLen;
    if (len> s.length) return [];

    const wordMap = {};
    for(let i=0;i<words.length;i++) {
       if(wordMap[words[i]] === undefined) {
            wordMap[words[i]] = 1
        } else {
            wordMap[words[i]] +=1;
        }
    }

    const res = []
    for(let i=0;i<s.length;i++) {
        let tempNum = 0;
        const tempMap = { ...wordMap };
        let j = i;
        while(tempNum < wordsCount){
            const str = s.substring(j, j + oneLen);
            if (!tempMap[str]) break;
            tempMap[str] -=1;
            tempNum++;
            j = j + oneLen;
        }

        if (tempNum === wordsCount){
            res.push(i)
        }
    }
    return res;
};

复杂度

时间 O(s.lengthk) k=s长度/word长度遍历一次 空间 O(m×n) 单词长度单词个数

[chenming-cao]

解题思路

哈希表。建立初始哈希表储存串联所有单词的子串的单词和对应出现次数。遍历字符串s确定子串起始点。每次先复制初始的哈希表，然后从起始点开始截取长度为words[i].length的子字符串，看该子字符串是否出现在哈希表中。如果没出现，则将起始点后移一位。如果出现，更新哈希表，出现次数减1，次数为0时则将Key从哈希表中删除。重复次循环继续截取长度为words[i].length的子字符串，直到哈希表为空。如果循环结束哈希表为空，表示子串中所有单词全部找到，将起始点存放到结果数组中，将起始点后移继续遍历。最后返回结果数组。

代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int slen = s.length();
        int num = words.length;
        int wlen = words[0].length();
        if (slen < num * wlen) return res;

        Map<String, Integer> wordMap = new HashMap<>();
        for (String word: words) {
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= slen - num * wlen; i++) {
            String sub = "";
            int start = i;         
            map.putAll(wordMap);
            do {
                sub = s.substring(start, start + wlen);
                if (!map.containsKey(sub)) break;
                int count = map.get(sub) - 1;
                if (count == 0) map.remove(sub);
                else map.put(sub, count);
                start += wlen;
            } while (!map.isEmpty());

            if (map.isEmpty()) res.add(i);
            map.clear();
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：令n为字符串s的长度，m为words的长度，l为每个单词的长度。如果将substring()函数操作数定为1，则为O(mn)。如果将substring()函数操作数定为l，则为O(mnl)
• 空间复杂度：O(m)，每次需要用到一个长度为m的哈希表。

[myleetcodejourney]

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        memo = collections.defaultdict(int) 

        m = len(words)
        n = len(words[0])

        if m*n > len(s): return []

        for word in words:
            memo[word] += 1

        res = []
        for i in range(len(s)):
            curr = s[i: i+ m*n]
            temp = collections.defaultdict(int) 
            j = 0

            while(j<m*n):
                sub_str = curr[j:j+n]
                if sub_str not in memo: break
                temp[sub_str]+=1

                if temp[sub_str] >memo[sub_str]: break
                j+=n

            if j == m * n:
                res.append(i)

        return res

[FlipN9]

/**
    思路:
    最好是可以一次遍历, 然后拿到所有的位置, 每次检查的长度为 所有 words 加起来的长度

    **滑动窗口式检查, 窗口一格格右移**
        对于每个 word, 检查它在窗口中出现的次数 ?= words 中出现的次数
        但是这样对于 按照单词长度倍数offset 的窗口来说, 中间的检查都是重复的    

    **优化**: 根据 起始点 在单词长度中的位置, offset=单词长度的倍数 进行偏移
    比如说 一个单词长度为 4, 那么 048, 159, 这样检查
        如果从头向后检查, 碰见没有出现过的 word 组合, 可以跳过之前检查的所有
                       如果只是 freq 出现太多了, 窗口右移一个 wL, 但是这样其实还是有很多重复的检查 108ms
        如果从后往前检查, 遇见 freq 出现次数过多或者没见过的 word 可以直接抛弃整个窗口
                       这样写方便和快太多了 9ms

    TC: O(wN + sL * wL) ==> 1. 遍历words列表 O(wN) 2. 对于每种起始位置遍历整个 s O(sL * wL)
    SC: O(wN)   ==> Hashmap
*/

// 对于每一个窗口从后向前
class Solution {
   public List<Integer> findSubstring(String s, String[] words) {
       List<Integer> res = new ArrayList<>();

       Map<String, Integer> wordToFreq = new HashMap<>();
       for (String w : words) {
           wordToFreq.put(w, wordToFreq.getOrDefault(w, 0) + 1);
       }

       int wN = words.length;
       int wL = words[0].length();
       int tL = wL * wN;
       int sL = s.length();

       if (tL > sL) return res;

       for (int k = 0; k < wL; k++) {                       // 起始点 从单词长度不同点开始
           for (int i = k; i + tL <= sL; i+= wL) {          // 从起始点开始遍历整个 s
               Map<String, Integer> tmp = new HashMap<>();
               for (int j = i + tL - wL; j >= i; j -= wL) {
                   String word = s.substring(j, j + wL);
                   // System.out.println(word);
                   int curFreq = tmp.getOrDefault(word, 0) + 1;
                   int needFreq = wordToFreq.getOrDefault(word, 0);
                   if (needFreq < curFreq) {
                       i = j;
                       break;
                   } else if (j == i) {
                       res.add(i);
                   } else {
                       tmp.put(word, curFreq);
                   }
               }
               // System.out.println();
           }
       }
       return res;
    }
}

[bookyue]

code

    public List<Integer> findSubstring(String s, String[] words) {
        int sLen = s.length();
        int n = words.length;
        int wLen = words[0].length();

        if (sLen < n * wLen) return List.of();

        Map<String, Integer> counts = new HashMap<>();
        for (String word : words)
            counts.put(word, counts.getOrDefault(word, 0) + 1);

        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i <= sLen - n * wLen; i++) {
            String sub = s.substring(i, i + n * wLen);
            if (isConcat(sub, counts, wLen))
                ans.add(i);
        }

        return ans;
    }

    private boolean isConcat(String sub, Map<String, Integer> counts, int wordLen) {
        Map<String, Integer> seen = new HashMap<>();
        for (int i = 0; i < sub.length(); i += wordLen) {
            String sWord = sub.substring(i, i + wordLen);
            if (!counts.containsKey(sWord)) return false;

            seen.put(sWord, seen.getOrDefault(sWord, 0) + 1);
            if (seen.get(sWord) > counts.get(sWord)) return false;
        }

        return true;
    }

[Abby-xu]

思路

（抄作业）滑动窗口+HashTable

代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        word_len = len(words[0])
        ori_word_dict = defaultdict(int)

        for word in words:
            ori_word_dict[word] += 1

        all_word_len = len(words) * word_len
        result = []
        for i in range(word_len):
            queue = deque()
            word_dict = ori_word_dict.copy()
            for j in range(i, len(s) - word_len + 1, word_len):
                word = s[j:j + word_len]
                if word_dict.get(word, 0) != 0:
                    word_dict[word] -= 1
                    queue.append(word)
                    if sum(word_dict.values()) == 0:
                        result.append(j - all_word_len + word_len)
                        last_element = queue.popleft()
                        word_dict[last_element] = word_dict.get(last_element, 0) + 1
                else:
                    while len(queue):
                        last_element = queue.popleft()
                        if last_element == word:
                            queue.append(word)
                            break
                        else:
                            word_dict[last_element] = word_dict.get(last_element, 0) + 1
                            if word_dict[last_element] > ori_word_dict[last_element]:
                                word_dict = ori_word_dict.copy()

        return result

复杂度

O(n*m)/O(n+m)

[zrtch]

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    words = words.sort()
    var wl = words[0].length;
    var l = words.length * wl;
    var res = [];
    if (s.length < l) return res;
    const regex = new RegExp(`.{${wl}}`, 'g')
    for (var i = 0; i < s.length; i+=1) {
        const ss = (s.substring(i, i+l).match(regex) || []).sort()
        if (ss.length===words.length && ss.every((_,j) => ss[j]===words[j])) {
            res.push(i)
        }
    }
    return res;
};

[testplm]

from collections import deque, defaultdict

class Solution(object):
    def findSubstring(self, s, words):
        # 使用哈系表加滑动窗口,滑动窗口的总长度不变
        word_len = len(words[0])
        ori_word_dict = defaultdict(int)
        # 创建关于words的字典
        for word in words:
            ori_word_dict[word] += 1
        # 这里是滑动窗口的长度,正好对应了单词组合的总长度
        all_word_len = len(words)*word_len
        result = []
        for i in range(word_len):
            # 初始化滑动窗口
            queue = deque()
            word_dict = ori_word_dict.copy()
            for j in range(i,len(s)-word_len+1,word_len):
                word = s[j:j+word_len]
                if word_dict.get(word, 0) != 0:
                    word_dict[word] -= 1
                    queue.append(word)
                    if sum(word_dict.values()) == 0:
                        result.append(j - all_word_len + word_len)
                        last_element = queue.popleft()
                        word_dict[last_element] = word_dict.get(last_element, 0) + 1
                else:
                    while len(queue):
                        last_element = queue.popleft()
                        if last_element == word:
                            queue.append(word)
                            break
                        else:
                            word_dict[last_element] = word_dict.get(last_element, 0) + 1
                            if word_dict[last_element] > ori_word_dict[last_element]:
                                word_dict = ori_word_dict.copy()
        return result

• Time:O(n*m)
• Space:O(n+m)

[suukii]

• Time: $O(n*(n-m))$, n is the length of s, m is the total length of all the words in words

• Space: $O(m)$, m is the size of words

  class Solution {
  public:
  vector<int> findSubstring(string s, vector<string>& words) {
      int word_len = words[0].size();
      int substr_len = word_len * words.size();
      vector<int> res;
  
      if (s.size() < substr_len) return res;
  
      unordered_map<string, int> available_words;
      for (auto& word : words)
          available_words[word]++;
  
      for (int i = 0; i <= s.size() - substr_len; i++) {
          unordered_map<string, int> words_count;
  
          for (int j = i; j <= i + substr_len - word_len; j += word_len)
              words_count[s.substr(j, word_len)]++;
  
          if (available_words == words_count) res.emplace_back(i);
      }
      return res;
  }
  };

[yuexi001]

思路

• 哈希表hashMap存储words中字符串出现次数
• 遍历s，取长度为word_num * word_length的子串，遍历该子串，取长度为word_length的串，将其出现次数存入哈希表temp。如果该串是串联子串，temp和hashMap的值相同，否则进入下一循环。

代码

C++ Code:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int>hashMap;
        int word_num = words.size(), word_length = words[0].size(), s_length = s.size();
        vector<int>res;

        for(const auto& word: words)
            hashMap[word]++;

        for(int i = 0; i < (s_length-word_num*word_length+1); i++){
            unordered_map<string, int>temp;
            string cur = s.substr(i,  word_num * word_length);

            int j = 0;
            for(; j < cur.size(); j += word_length){
                string str = cur.substr(j, word_length);
                if(!hashMap.count(str)) break;
                temp[str]++;
                if(temp[str] > hashMap[str]) break;
            }

            if(j == cur.size())
                res.push_back(i);
        }

        return res;
    }
};

复杂度分析

令 n 为字符串 S 长度, m 为 words 数组元素个数, k 为单个 word 字串长度。

• 时间复杂度：$O(nmk)$
• 空间复杂度：$O(m)$

[Alyenor]

function findSubstring(s: string, words: string[]): number[] {
    let res=[]
    const n=s.length,m=words.length,w=words[0].length
    let tot=new Map<string,number>()
    for(const word of words){
        tot.set(word,1+(tot.has(word)?tot.get(word)!:0))
    }
    for(let i=0;i<w;i++){
        let wd = new Map<string,number>()
        let cnt=0
        for(let j=i;j+w<=n;j+=w){
            if(j>=i+m*w){
                let word=s.substring(j-m*w,j-m*w+w)
                wd.set(word,(wd.has(word)?wd.get(word)!:1)-1)
                if(tot.has(word) && wd.get(word) < tot.get(word)) cnt--
            }
            let word=s.substring(j,j+w)
            wd.set(word,1+(wd.has(word)?wd.get(word)!:0))
           if(tot.has(word) && wd.get(word) <= tot.get(word)) cnt++
            if(cnt === m) res.push(j-(m-1)*w)
        }
    }
    return res
};

[tiandao043]

思路

暴力，俩hash，第一回超时了，修改了循环的终值。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int n=s.length();
        int wordn=words[0].size();
        int m=words.size();
        map<string, int> mp;
        for(int i =0;i<m;i++){
            mp[words[i]]++;
        }
        for(int i=0;i<=n-m*wordn;i++){
            string temp=s.substr(i,m*wordn);
            int k=0;
            int cnt=0;
            map<string, int> tmp;
            for(k=0;k<m*wordn;k+=wordn){    
                // cout<<temp.substr(k,wordn)<<endl;
                if(!mp.count(temp.substr(k,wordn))){
                    break;
                }else{
                    tmp[temp.substr(k,wordn)]++;
                    if(tmp[temp.substr(k,wordn)]>mp[temp.substr(k,wordn)]){
                        break;
                    }                    
                    cnt++;
                }
            }
            if(k<m*wordn){
            }else{
                if(cnt==m){
                    ans.push_back(i);
                }

            }
        }
        return ans;
    }
};

O(n∗m∗k) O(m+n)空间复杂度是哈希表的长度，不知道需不需要乘以哈希表的每个单位长度。

思路

滑动窗口，不枚举了，右边扩张左边收缩，利用上回的信息。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (words.size() == 0) return {};
        unordered_map<string, int> need, window;

        for (string w : words) need[w]++;
        int len=words[0].length();

        int left = 0, right = 0;
        int valid = 0;
        vector<int> res; // 记录结果
        int i=0;
        while(i<len){
            left=i++;
            right=left;
            window.clear();valid = 0;
            while (right < s.size()) {
            string c = s.substr(right,len);
            // cout<<c<<endl;
            right+=len;
            // 进行窗口内数据的一系列更新
            if (need.count(c)) {
                window[c]++;
                // right+=len;
                if (window[c] == need[c]) 
                    valid++;
            }
            // 判断左侧窗口是否要收缩
            while ((right - left) >= (words.size()*len)) {
                // 当窗口符合条件时，把起始索引加入 res
                if (valid == need.size())
                    res.push_back(left);
                string d = s.substr(left,len);
                // cout<<d<<endl;
                left+=len;
                // 进行窗口内数据的一系列更新
                if (need.count(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
            }
        }
    }
        }
    return res;   
    }
};

[gsw9818]

滑动窗口

代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        cnt, l = len(words), len(words[0])
        i, j = 0, cnt * l - 1
        ans = []
        check = collections.Counter(words)
        while j < len(s):
            ss = s[i : j + 1]
            tmp = []
            for k in range(0, len(ss), l):
                tmp.append(ss[k: k + l])
            if collections.Counter(tmp) == check:
                ans.append(i)
            i += 1
            j += 1
        return ans

[xuanaxuan]

思路

• 题目给的words是可以有重复项的，所以要用哈希表map1记录每项出现的次数。
• 遍历s,取出子串为words.length*words[0].length(目标子串的长度),按words[0].length长度切割，用map2记录单词出现的次数，一旦次数超过map1或者单词并不存在map1中时，说明这次遍历的子串不满足条件，提前break;
• 没有提前break的子串就是符合条件的，怎么获取这部分呢？可以通过判断for循环的变量是否等于循环的次数。 代码

  var findSubstring = function (s, words) {
  const res = [], wordsLen = words[0].length, resLen = wordsLen * words.length;
  let map = words.reduce((totalMap, cur) => {
    totalMap.set(cur, (totalMap.get(cur) || 0) + 1)
    return totalMap
  }, new Map())
  let r = 0;
  while (r < s.length - resLen + 1) {
    let mapT = new Map()
    const curTotalStr = s.slice(r, r + resLen)
    let i = 0
    for (; i < resLen; i += wordsLen) {
        const curStr = curTotalStr.slice(i, i + wordsLen)
        if (!map.has(curStr)) break;
        mapT.set(curStr, (mapT.get(curStr) || 0) + 1)
        if (map.get(curStr) < mapT.get(curStr)) break;
    }
    if (i == resLen) {
        res.push(r)
    }
    r += 1
  }
  return res
  };

  复杂度

令 n 为字符串 S 长度, m 为 words 数组元素个数, k 为单个 word 字串长度。

时间复杂度：O(m+w×n) 空间复杂度： O(m)

[chiehw]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int totalLen = s.length();
        int len = words[0].length();
        int n = words.length;
        if (n*totalLen == 0){
            return result;
        }
        HashMap<String,Integer> wordMap = new HashMap<>();
        for (String word:words) {
            int value = wordMap.getOrDefault(word, 0);
            wordMap.put(word,value+1);
        }
        
        for (int i = 0; i <totalLen-n*len+1; i++) {
          
            Map<String,Integer> hasWords = new HashMap<>();
            int num = 0;
            while (num < n){
                String currWord = s.substring(i+num*len,i+(num+1)*len);
                if (wordMap.containsKey(currWord)){
                    int value = hasWords.getOrDefault(currWord,0);
                    hasWords.put(currWord,value+1);
                    if (wordMap.get(currWord) < hasWords.get(currWord)){
                        break;
                    }
                }else {
                    break;
                }
                num++;
            }
            if (num == n){
                result.add(i);
            }
        }
        return result;
    }
}

[AstrKing]

思路

滑动窗口，没看太懂，先提交了

代码

class Solution {

    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> res = new ArrayList<>();

        Map<String, Integer> map = new HashMap<>();

        if (words == null || words.length == 0)
            return res;

        for (String word : words)
            map.put(word, map.getOrDefault(word, 0) + 1);

        int sLen = s.length(), wordLen = words[0].length(), count = words.length;

        int match = 0;

        for (int i = 0; i < sLen - wordLen * count + 1; i++) {

            //得到当前窗口字符串
            String cur = s.substring(i, i + wordLen * count);
            Map<String, Integer> temp = new HashMap<>();
            int j = 0;

            for (; j < cur.length(); j += wordLen) {

                String word = cur.substring(j, j + wordLen);
                // 剪枝
                if (!map.containsKey(word))
                    break;

                temp.put(word, temp.getOrDefault(word, 0) + 1);
                // 剪枝
                if (temp.get(word) > map.get(word))
                    break;
            }

            if (j == cur.length())
                res.add(i);
        }

        return res;
    }
}

复杂度分析

令 n 为字符串 S 长度, m 为 words 数组元素个数, k 为单个 word 字串长度。

时间复杂度: 本质上我们的算法是将 s 划分为若干了段，这些段的长度为 m km∗k，对于每一段我们最多需要检查 n - m kn−m∗k 次，因此时间复杂度为 O(n m k)O(n∗m∗k)。

空间复杂度: temp 在下一次循环会覆盖上一次的 temp，因此 temp 的空间在任意时刻都不大于 O(m)O(m), 因此空间复杂度为 O(m)O(m)。

[want2333]

【Day 23】30. 串联所有单词的子串

class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word: words) {
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};

[klspta]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList();
        if (s == null || s.length() == 0 || words == null || words.length == 0){
             return res;
        }
        int n = s.length();
        int m = words.length;
        int w = words[0].length();

        //预处理，统计 words 中每个单词的数量
        Map<String, Integer> total = new HashMap();
        for (String word : words) {
            total.put(word, total.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i < w; ++i) {
            HashMap<String, Integer> wd = new HashMap<>();
            // 统计窗口内单词在 words 中出现的次数
            int cnt = 0; 
            for (int j = i; j + w <= n; j += w) {
                //窗口已经满，需要去掉窗口最左边的单词，才能在窗口中添加新的单词
                if (j >= i + w * m) {
                    //获取窗口最左边的单词
                    String word = s.substring(j - m * w, w + j - m * w); 
                    //去除窗口最左边的单词
                    wd.put(word, wd.get(word) - 1); 
                    if (total.get(word) != null && wd.get(word) < total.get(word))
                        cnt--;
                }
                String word = s.substring(j, j + w); 
                wd.put(word, wd.getOrDefault(word, 0) + 1); //在窗口最右边添加新的单词
                if (total.get(word) != null && wd.get(word) <= total.get(word)){
                    cnt++;
                }
                if (cnt == m){
                    res.add(j - (m - 1) * w);
                }
            }
        }
        return res; 
    }
}

[aouos]

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
  const wordSize = words[0].length;
  const wordsLen = wordSize * words.length;
  let map = new Map();
  let ans = [];
  for (let i = 0; i< words.length; i++) {
    map.has(words[i]) ? map.set(words[i], map.get(words[i]) + 1) : map.set(words[i], 1);
  }
  for (let i = 0; i < s.length - wordsLen + 1; i++) {
    const tmap = new Map(map);
    let count = words.length;
    for (let p = i; p < i + wordsLen; p += wordSize) {
      const word = s.slice(p, p + wordSize);
      if (!tmap.has(word) || tmap.get(word) <= 0) {
        break;
      }
      tmap.set(word, tmap.get(word) - 1);
      count--;
    }
    if (count === 0) {
      ans.push(i);
    }
  }
  return ans;
};

[RestlessBreeze]

思路

滑动窗口

代码

class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word: words) {
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};

[Albert556]

class Solution { public: vector findSubstring(string &s, vector &words) { vector res; int m = words.size(), n = words[0].size(), ls = s.size(); for (int i = 0; i < n && i + m n <= ls; ++i) { unordered_map<string, int> differ; for (int j = 0; j < m; ++j) { ++differ[s.substr(i + j n, n)]; } for (string &word: words) { if (--differ[word] == 0) { differ.erase(word); } } for (int start = i; start < ls - m n + 1; start += n) { if (start != i) { string word = s.substr(start + (m - 1) n, n); if (++differ[word] == 0) { differ.erase(word); } word = s.substr(start - n, n); if (--differ[word] == 0) { differ.erase(word); } } if (differ.empty()) { res.emplace_back(start); } } } return res; } };

[Elsa-zhang]

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        res = []
        m, n, ls = len(words), len(words[0]), len(s)
        for i in range(n):
            if i + m * n > ls:
                break
            differ = Counter()
            for j in range(m):
                word = s[i + j * n: i + (j + 1) * n]
                differ[word] += 1
            for word in words:
                differ[word] -= 1
                if differ[word] == 0:
                    del differ[word]
            for start in range(i, ls - m * n + 1, n):
                if start != i:
                    word = s[start + (m - 1) * n: start + m * n]
                    differ[word] += 1
                    if differ[word] == 0:
                        del differ[word]
                    word = s[start - n: start]
                    differ[word] -= 1
                    if differ[word] == 0:
                        del differ[word]
                if len(differ) == 0:
                    res.append(start)
        return res

[Alexno1no2]

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:return []
        one_word_len = len(words[0])
        all_words_len = len(words) * one_word_len
        n = len(s)
        words_counter = collections.Counter(words)
        res = []
        for i in range(0, n - all_words_len + 1):
            tmp = s[i:i+all_words_len]
            c_tmp = []
            for j in range(0, all_words_len, one_word_len):
                c_tmp.append(tmp[j:j+one_word_len])
            if collections.Counter(c_tmp) == words_counter:
                res.append(i)
        return res

[zhuzhu096]

class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: res = [] m,w = len(words),len(words[0]) M = {} for it in words: if it not in M.keys(): M[it] = 1 else: M[it] += 1 for i in range(w): S = {} j,cnt = i,0 while j + w <= len(s): if w m <= j: t = s[j - w m : j - w (m - 1)] S[t] -= 1 if t in M.keys() and S[t] < M[t]: cnt -= 1 t = s[j:j + w] if t not in S.keys(): S[t] = 1 else: S[t] += 1 if t in M.keys() and S[t] <= M[t]:cnt += 1 if m == cnt: res.append(j - w (m - 1)) j += w return res

[A-pricity]

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    let wordlen=words[0].length;
    let ans=[];
    let sub=[]
    words.sort();
    let str1=words.toString()
    for(let i=0;i<s.length;i++){
        for(let j=0;j<words.length;j++){
            sub.push(s.substr(i+wordlen*j,wordlen))

        }
        sub.sort()
        if(sub.toString()===str1){
            ans.push(i)
        }
        sub=[]
    }
    return ans
};

[wtdcai]

代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        from collections import Counter
        if not s or not words:
            return []
        one_l = len(words[0])
        allword = len(words)
        strlen = len(s)
        words = Counter(words)
        res = []
        for i in range(0,one_l):
            head_count = 0
            left = i
            right = i
            cur_counter = Counter()
            while right + one_l <= strlen:
                w = s[right:right+one_l]
                right += one_l
                cur_counter[w] += 1
                head_count += 1
                while cur_counter[w] >words[w]:
                    l_w = s[left:left+one_l]
                    left += one_l
                    cur_counter[l_w] -= 1
                    head_count -= 1
                if head_count == allword:
                    res.append(left)
        return res

复杂度分析

O(n)
O(1)

[BruceZhang-utf-8]

思路

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
ArrayList<Integer> res = new ArrayList<>();
        if(words==null || words.length==0) return res;
        //将words存入map
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }
        //字符串的长度
        int length=s.length();
        //单个word的长度
        int wLen = words[0].length();
        //words的个数
        int count=words.length;
        //按照words的总长度进行截断s
        for (int i = 0; i < length-wLen*count+1; i++) {
            //按照words的总长度进行截断
            String curr = s.substring(i, i + wLen * count);
            HashMap<String, Integer> temp = new HashMap<>();
            //针对curr进行遍历，长度为words中每个元素的长度来遍历
            int j = 0;
            for (; j < curr.length(); j+=wLen) {
                //获取单独一个word长度的字符
                String word = curr.substring(j, j + wLen);
                if(!map.containsKey(word)) break;
                temp.put(word,temp.getOrDefault(word,0)+1);
                if(temp.get(word)>map.get(word)) break;

            }
            if(j==curr.length()) res.add(i);

        }
return res;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[paopaohua]

思路

哈希表 + 双指针

代码

class Solution {

public List<Integer> findSubstring(String s, String[] words) {

    List<Integer> res = new ArrayList<>();

    Map<String, Integer> map = new HashMap<>();

    if (words == null || words.length == 0)
        return res;

    for (String word : words)
        map.put(word, map.getOrDefault(word, 0) + 1);

    int sLen = s.length(), wordLen = words[0].length(), count = words.length;

    int match = 0;

    for (int i = 0; i < sLen - wordLen * count + 1; i++) {

        //得到当前窗口字符串
        String cur = s.substring(i, i + wordLen * count);
        Map<String, Integer> temp = new HashMap<>();
        int j = 0;

        for (; j < cur.length(); j += wordLen) {

            String word = cur.substring(j, j + wordLen);
            // 剪枝
            if (!map.containsKey(word))
                break;

            temp.put(word, temp.getOrDefault(word, 0) + 1);
            // 剪枝
            if (temp.get(word) > map.get(word))
                break;
        }

        if (j == cur.length())
            res.add(i);
    }

    return res;
}

}

### 复杂度
- 时间：o(n*m*k)
- 空间：o(m)

[Jetery]

30. 串联所有单词的子串

思路

滑动窗口 + 哈希表

代码 (cpp)

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        unordered_map<string, int> search;
        for (auto &word : words) ++search[word];
        int n = s.size(), m = words.size(), len = words[0].size();
        for (int i = 0, j = 0; i < n - m * len + 1; ++i) {
            unordered_map<string, int> sub; 
            for (j = 0; j < m; ++j) {
                auto word = s.substr(i + j * len, len);
                if (!search.count(word)) break; 
                if (++sub[word] > search[word]) break;
            }
            if (j == m) res.push_back(i);
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[neado]

思路

代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
          List<Integer> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        if (words == null || words.length == 0)
            return res;
        for (String word : words)
            map.put(word, map.getOrDefault(word, 0) + 1);
        int sLen = s.length(), wordLen = words[0].length(), count = words.length;
        int match = 0;
        for (int i = 0; i < sLen - wordLen * count + 1; i++) {
            //得到当前窗口字符串
            String cur = s.substring(i, i + wordLen * count);
            Map<String, Integer> temp = new HashMap<>();
            int j = 0;
            for (; j < cur.length(); j += wordLen) {
                String word = cur.substring(j, j + wordLen);
                // 剪枝
                if (!map.containsKey(word))
                    break;
                temp.put(word, temp.getOrDefault(word, 0) + 1);
                // 剪枝
                if (temp.get(word) > map.get(word))
                    break;
            }
            if (j == cur.length())
                res.add(i);
        }
        return res;
    }
}

算法复杂度

TIME:O(mnk) SPACE:O(m)

[Frederickfan]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList();
        if (s == null || s.length() == 0 || words == null || words.length == 0){
             return res;
        }
        int n = s.length();
        int m = words.length;
        int w = words[0].length();

        //预处理，统计 words 中每个单词的数量
        Map<String, Integer> total = new HashMap();
        for (String word : words) {
            total.put(word, total.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i < w; ++i) {
            HashMap<String, Integer> wd = new HashMap<>();
            // 统计窗口内单词在 words 中出现的次数
            int cnt = 0; 
            for (int j = i; j + w <= n; j += w) {
                //窗口已经满，需要去掉窗口最左边的单词，才能在窗口中添加新的单词
                if (j >= i + w * m) {
                    //获取窗口最左边的单词
                    String word = s.substring(j - m * w, w + j - m * w); 
                    //去除窗口最左边的单词
                    wd.put(word, wd.get(word) - 1); 
                    if (total.get(word) != null && wd.get(word) < total.get(word))
                        cnt--;
                }
                String word = s.substring(j, j + w); 
                wd.put(word, wd.getOrDefault(word, 0) + 1); //在窗口最右边添加新的单词
                if (total.get(word) != null && wd.get(word) <= total.get(word)){
                    cnt++;
                }
                if (cnt == m){
                    res.add(j - (m - 1) * w);
                }
            }
        }
        return res; 
    }
}

[Ryanbaiyansong]

··· class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: need = defaultdict(int) for word in words: need[word] += 1 n = len(s) m = len(words) w = len(words[0]) res = []

分类所有w的起始位置

    for i in range(0, w):
        window = defaultdict(int)
        cnt = 0

        j = i
        # 起始下标在j, 长度为w的最后一个单词的下表是 j + w - 1 <= n - 1 => j + w <= n
        # 遍历 0, w, 2w, 3w....
        #     1, w + 1, 2w + 1 ....
        #     2, w + 2, 3w + 2
        # 遍历从i开始的所有起始点下标
        while j + w <= n:
            # i + m * w 是 原来的位置, 需要删左边的
            if j >= i + m * w:
                word = s[j - m * w: j - m * w + w]
                window[word] -= 1
                if window[word] < need[word]:
                    cnt -= 1

            # 现在的单词是s[j: j + w]
            word = s[j: j + w]
            # 当前窗口的单词数 + 1
            window[word] += 1

            if window[word] <= need[word]: cnt += 1

            if cnt == m:
                res.append(j - (m - 1) * w)

            j += w

    return res

···

[Yongxi-Zhou]

思路

双指针

代码

    class Solution:
        def findSubstring(self, s: str, words: List[str]) -> List[int]:
            counter = Counter(words)
            sLen = len(s)
            n = len(words)
            wordLen = len(words[0])
            res = []

    #         iterate windows
            for i in range(sLen - n * wordLen + 1):
    #             当前window的可能，从i开始
                cur = s[i:i + wordLen * n]
                j = 0
    #         收集当前cur的每个词的频率，如果跟counter不一样就剪枝
                temp = collections.defaultdict(int)
                while j < len(cur):
                    word = cur[j: j + wordLen]
                    # print(word)
                    if word not in counter:
                        break

                    temp[word] += 1
                    if temp[word] > counter[word]:
                        break
                    j += wordLen
                if j == len(cur):
                    res.append(i)
            return res

复杂度

time O(N * M) space O(1)

[sclihuiming]

func findSubstring(s string, words []string) []int {
    strLen := len(s)
    wordCount := len(words)
    wordLen := len(words[0])

    wordDict := map[string]int{}
    for _, word := range words {
        wordDict[word] += 1
    }

    validLen := wordCount * wordLen
    res := []int{}
    for index := 0; index < strLen-validLen+1; index++ {
        currentEndIndex := index + validLen
        curStr := s[index:currentEndIndex]
        matchDict := map[string]int{}

        j := 0
        for ; j < currentEndIndex-index; j += wordLen {
            word := curStr[j : j+wordLen]
            if _, ok := wordDict[word]; !ok {
                break
            }
            matchDict[word] += 1
            if matchDict[word] > wordDict[word] {
                break
            }
        }

        if j == currentEndIndex-index {
            res = append(res, index)
        }
    }
    return res
}

[whoam-challenge]

思路

滑动窗口

代码

class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: res = [] m, n, ls = len(words), len(words[0]), len(s) for i in range(n): if i + m n > ls: break differ = Counter() for j in range(m): word = s[i + j n: i + (j + 1) n] differ[word] += 1 for word in words: differ[word] -= 1 if differ[word] == 0: del differ[word] for start in range(i, ls - m n + 1, n): if start != i: word = s[start + (m - 1) n: start + m n] differ[word] += 1 if differ[word] == 0: del differ[word] word = s[start - n: start] differ[word] -= 1 if differ[word] == 0: del differ[word] if len(differ) == 0: res.append(start) return res

复杂度分析

• 时间复杂度分析 O(s的长度 * words中单词的长度)
• 空间复杂度分析 O（words中单词个数*words中单词的长度）