【Day 23 】2022-01-03 - 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"] 输出：[]

[LiFuQuan1208]

思路：

自己写了半天还是 卡在了各种考虑的不到位 还是贴题解吧

代码：

     public List<Integer> findSubstring(String s, String[] words) {
      List<Integer> res = new ArrayList<>();
        Map<String, Integer> wordMap = new HashMap<>();
        if (words == null || words.length == 0)
            return res;
        for (String word : words)
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        int sLen = s.length();
        int wordLen = words[0].length();
        int wordsLen = words.length;
        for (int i = 0; i < sLen - wordLen * wordsLen + 1; i++) {
            String cur = s.substring(i, i + wordLen * wordsLen);
            Map<String, Integer> temp = new HashMap<>();
            int j=0; 
            for (; j < cur.length(); j += wordLen) {
                String word = cur.substring(j, j + wordLen);
                if (!wordMap.containsKey(word))
                    break;
                temp.put(word, temp.getOrDefault(word, 0) + 1);
                if (temp.get(word) > wordMap.get(word))
                    break;
            }
            if (j == cur.length())
                res.add(i);
        }
        return res;
    }

[spacker-343]

思路

使用一个 map 统计字符串，然后遍历可能的开始位置，然后再设置一个指针从 0 开始遍历判断字符串，如果最后这个指针的位置等于 total 说明匹配成功，然后添加 i 进 result 中。

代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> counts = new HashMap<>();
        for (String str : words) {
            counts.put(str, counts.getOrDefault(str, 0) + 1);
        }
        int len = words[0].length();
        int total = words.length;
        int n = s.length();
        List<Integer> res = new ArrayList<>(); 
        for (int i = 0; i < n - total * len + 1; i++) {
            int j = 0;
            Map<String, Integer> seen = new HashMap<>();
            while (j < total) {
                String word = s.substring(i + j * len, i + (j + 1) * len);
                if (counts.containsKey(word)) {
                    seen.put(word, seen.getOrDefault(word, 0) + 1);
                    if (seen.get(word) > counts.get(word)) {
                        break;
                    }
                } else {
                    break;
                }
                j++;
            }
            if (j == total) {
                res.add(i);
            }
        }
        return res;
    }
}

[bluetomlee]

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        // 两个hash比对字符串的单元
        // 第一个hash->a存放words里每个string的出现个数
        // 第二个hash存->b放s里对应单个words里的每个单词出现个数，
        // 当b中出现过a里的，累加，如果b中次数>a里的，或者b中出现a未出现过的咋没有索引
        vector<int> ret;
        if(words.size() == 0)//判断words为空,因为下面用到了words[0]
            return ret;

        int word_size = words[0].size();
        int word_num = words.size();

        unordered_map<string,int> m1;//构造hashmap
        for(int i=0;i<word_num;i++)
            m1[words[i]]++;

        unordered_map<string,int> m2;
        for(int i=0; (i + word_size * word_num) <= s.size() ; i++){//截取的s符合题意
            int j = 0;
            for(j=i;j < (i + word_size * word_num) ; j=j+word_size){//分段判断
                string temp_str = s.substr(j,word_size);
                if(m1[temp_str] == 0){//m1中没有截取的串，直接跳出
                    break;
                }else{
                    m2[temp_str]++;
                    if(m1[temp_str] < m2[temp_str])//重复次数过多，也跳出
                        break;
                }
            }

            if(j == (i + word_size * word_num))//每一段都符合，则加入答案
                ret.push_back(i);

            m2.clear();//清空m2
        }
        return ret;
    }
};

[ZZRebas]

思路

使用itertools.permutations排列函数统计words排列的组合， 然后遍历所有的排列，判断是否在字符串中。

代码(Python)

from itertools import permutations
def fun(s,words):
    words_list = list(permutations(words,len(words)))
    # print(d)
    out_list=[]
    for tuple_words in words_list:
        str_words=''.join(tuple_words)
        if str_words in s:
            out_list.append(s.index(str_words))
    print(out_list)

s = "barfoothefoobarman"
words = ["foo","bar"]
# s = "wordgoodgoodgoodbestword"
# words = ["word","good","best","word"]
fun(s,words)    #[9, 0]

复杂度分析

• 时间复杂度： O(N)，N为字符串长度。
• 空间复杂度：

[SeventeenCui]

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if (words.empty()) return res;
        int n = s.size(), m = words.size(), w = words[0].size();
        unordered_map<string, int> tot;
        for (auto& word : words) tot[word] ++ ;

        for (int i = 0; i < w; i ++ ) {
            unordered_map<string, int> wd;
            int cnt = 0;
            for (int j = i; j + w <= n; j += w) {
                if (j >= i + m * w) {
                    auto word = s.substr(j - m * w, w);
                    wd[word] -- ;
                    if (wd[word] < tot[word]) cnt -- ;
                }
                auto word = s.substr(j, w);
                wd[word] ++ ;
                if (wd[word] <= tot[word]) cnt ++ ;
                if (cnt == m) res.push_back(j - (m - 1) * w);
            }
        }

        return res;
    }
};

[LAGRANGIST]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res=new ArrayList<>();
        if (words==null||words.length==0)return res;
        int wordNum = words.length,wordLen=words[0].length();
        HashMap<String,Integer> allWords=new HashMap<>();
        for (String word : words) {
            Integer value = allWords.getOrDefault(word, 0);
            allWords.put(word,++value);
        }
        for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
            HashMap<String,Integer> hasWords=new HashMap<>();
            int count=0;
            while (count<wordNum){
                String word = s.substring(i + count * wordLen, i + (count + 1) * wordLen);
                if (allWords.containsKey(word)){
                    Integer value = hasWords.getOrDefault(word, 0);
                    hasWords.put(word,++value);
                    if (hasWords.get(word)>allWords.get(word))break;
                }else {
                    break;
                }
                count++;
            }
            if (count==wordNum)res.add(i);
        }
        return res;
    }
}

[KennethAlgol]

思路

使用HashMap

语言

java

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;
        HashMap<String, Integer> map = new HashMap<>();
        int one_word = words[0].length();
        int word_num = words.length;
        int all_len = one_word * word_num;
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < s.length() - all_len + 1; i++) {
            String tmp = s.substring(i, i + all_len);
            HashMap<String, Integer> tmp_map = new HashMap<>();
            for (int j = 0; j < all_len; j += one_word) {
                String w = tmp.substring(j, j + one_word);
                tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
            }
            if (map.equals(tmp_map)) res.add(i);
        }
        return res;
    }
}

复杂度分析

时间复杂度 O(n^2) 空间复杂度 O(n)

[linrAx]

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;
    }
}

[Yachen-Guo]

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        HashSet<String> wordSet = new HashSet<>();
        for(String str : words)
            wordSet.add(str);

        if(words.length == 0 || s.length() == 0)       return res;
        int len = words[0].length();
        int num = words.length;

        for(int i = 0; i < s.length(); i++)
        {
            List<String> marked = new ArrayList<>();
            for(String str : words)   
                marked.add(str);

            int j = i + len * num;
            if(j > s.length())      continue;

            String frac = s.substring(i, j);

            for(int k = 0; k <= j-i - len; k += len)
            {
                String singleStr = frac.substring(k, k+len);
                if(!marked.contains(singleStr))
                    break;
                else
                    marked.remove(singleStr);
            }
            if(marked.size() == 0)
                res.add(i);
        }
        return res;
    }
}

[fornobugworld]

困难有点难，直接看答案。。 class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: allWords = collections.Counter(words) wordNum = len(words) wordLen = len(words[0]) res = [] for i in range(len(s) - wordNum wordLen + 1): subWords = collections.defaultdict(int) index = i while index < i + wordNum wordLen: curWord = s[index: index + wordLen] if curWord not in allWords or subWords[curWord] == allWords[curWord]: break subWords[curWord] += 1 index += wordLen if index == i + wordNum * wordLen: res.append(i) return res

[MongoCZK]

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
    const wordSize = words[0].length;
    const substringLen = wordSize * words.length;

    const wordsCount = {};
    words.forEach(w => (wordsCount[w] = (wordsCount[w] || 0) + 1));

    const res = [];
    for (let i = 0; i <= s.length - substringLen; i++) {
        const tempCount = { ...wordsCount };
        let count = words.length;

        for (let j = i; j < i + substringLen; j += wordSize) {
            const word = s.slice(j, j + wordSize);

            if (!(word in tempCount) || tempCount[word] <= 0) break;

            tempCount[word]--;
            count--;
        }

        if (count === 0) res.push(i);
    }
    return res;
};

[z1ggy-o]

思路

因为单词是定长的，我们可以计算长度得到 substring 和 substring 中的单词。

输入得到的单词组所能实现的组合太多，全部列出的话复杂度太高。 换个方式，我们可以数每个 substring 中有几个给定单词组中的单词出现了，各出现了几次。 如果出现的单词和次数都吻合，则说明配对成功。

代码

CPP

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int wlen;  // all words have the same length
        int wnum;
        vector<int> ret;
        unordered_map<string, int> target;

        if (!words.size())
            return ret;

        for (auto &w : words)
            target[w]++;

        wnum = words.size();
        wlen = words[0].size();
        for (int i = 0; i < s.size() - wnum*wlen + 1; i++) {
            unordered_map<string, int> occur;
            bool match = true;
            for (int j = 0; j < wnum; j++) {
                auto w = s.substr(i+j*wlen, wlen);
                if (target.count(w)) {
                    occur[w]++;
                }
            }

            if (occur.size() != target.size())
                continue;

            for (auto &[k, v] : occur) {
                if (v != target[k]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                ret.push_back(i);
            }
        }
        return ret;
    }
};

复杂度分析

• 时间：O(nkl), n 是 string 长度，k 给的单词个数，l 为各个单词的长度
• 空间：O(k*l), 一个 substring 的长度

[noperoc]

思路

• 需要重新做

代码

• 语言支持：Java

Java Code:

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;
    }
}

[for123s]

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> allWordsMap;
        for (auto& v : words) {
            ++allWordsMap[v];
        }

        int num = words.size();
        int onelen = words[0].length();
        vector<int> res;
        if (s.length() < num * onelen) {
            return res;
        }

        for (int left = 0; left < s.length() - num * onelen + 1; ++left) {
            unordered_map<string, int> nowWordsMap;
            int right = left;
            while (right < left + num * onelen) {
                auto cur = s.substr(right, onelen);
                if (allWordsMap.find(cur) == allWordsMap.end() 
                    || nowWordsMap[cur] == allWordsMap[cur]) {
                    break;
                }

                ++nowWordsMap[cur];
                right += onelen;
            }

            if (right == left + num * onelen) {
                res.emplace_back(left);
            }
        }

        return res;
    }
};

[machuangmr]

代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
              // 利用两个hash表存储单词出现的次数，再维护一个滑动窗口
        Map<String, Integer> allWords = new HashMap<>();
        for(String word: words){
            allWords.put(word, allWords.getOrDefault(word, 0) + 1);
        }        
        int wordNum = words.length, wordLen = words[0].length();
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i < s.length() - wordNum * wordLen + 1;i++){
            Map<String, Integer> subWords = new HashMap<>();
            int index = i;
            while(index <i + wordNum * wordLen) {
                String curWord = s.substring(index, index + wordLen);
                if(!allWords.containsKey(curWord) || allWords.get(curWord).equals(subWords.get(curWord))) {
                    break;
                }
                subWords.put(curWord, subWords.getOrDefault(curWord, 0) + 1);
                index += wordLen;
            }
            if(index == i + wordNum * wordLen) {
                res.add(i);
            }
        }
        return res;
        }
}

复杂度

• 时间复杂度O(N*M) N 为字符串长度， M为单词个数
• 空间复杂度O(M)

[QianShi-ffg]

用一个 unordered_map<string, int> need存储words中每个词的出现次数 遍历字符串的每个字符位置，。从该位置起不断截取word长度的子串，判断该word是否出现在need中。同时通过建立一个unordered_map<string, int> window保存当前单词的出现次数。如果window与need的所有单词次数相同，则记录当前子串起始位置

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> need;
        vector<int> ret;
        if(s.empty() || words.empty()) return ret;
        int wordNum = words.size(), wordLen = words[0].size();
        if (wordLen * wordNum > s.size()) return ret;
        // 统计word次数
        for(string s:words)
            need[s] ++;

        // 遍历所有子串 注意最后一个可能子串的起始坐标为s.size() - wordNum * wordLen
        for (int i = 0; i <= s.size() - wordNum * wordLen ; i++) {
            unordered_map<string, int> window;
            int cnt = 0;
            int begin = i;
            int match = 0;  // 匹配的词数目
            while (cnt < wordNum){
                string sub = s.substr(begin,wordLen);
                cnt ++;     // 当前子串的单词计数
                begin += wordLen;
                if(need.count(sub)){
                    window[sub] ++;
                    if(window[sub] == need[sub])
                        match ++;
                    else if(window[sub] > need[sub]){
                        match --;
                        break;
                    }
                } else
                    break;
            }

            if(match == need.size())
                ret.push_back(i);
        }

        return ret;
    }
};

[Tomtao626]

思路

• 滑动窗口

  代码

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

  复杂度

• 时间:O(n)

• 空间:O(n)

[chenyaohn]

思路

滑动窗口。保存word数组中字符串分别出现了多少次，同时留一个位置保存这个字段在遍历时出现的次数。每次遍历与word子串长度相等的s的子串时，统计s的子串是否在是word数组中出现过的，如出现过则其次数+1，如果这个次数大于在word数组中出现的次数，或者子串未在word数组中出现过，此次遍历结束。遍历结束后判断在之前的遍历word数组中的子串是否全部出现过。如是则证明表示其包含word数组中所有单词。滑动坐标进行下一次遍历。
https://leetcode-cn.com/submissions/detail/254678211/

代码

public class Day23 {

    /**
     * 1 <= s.length <= 104
     * s 由小写英文字母组成
     * 1 <= words.length <= 5000
     * 1 <= words[i].length <= 30
     * words[i] 由小写英文字母组成
     *"foobarfoobarthefoobarman"
     * ["foo","bar"]
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
//123 132 213 231 312 321  3*2*1  4321
        List<Integer> res = new ArrayList<>();
        int wordLength = words[0].length();//每个word的长度

        if(wordLength>s.length()){
            return res;
        }else if(wordLength==s.length()){
            if(words.length==1 && words[0].equals(s)){
                res.add(0);
            }
            return res;
        }
        HashMap<String,int[]> wordsMap = new HashMap<>();//key-word value[0]-在共出现多少次 value[1]-当前遍历s时出现了多少次，默认0
        for (int i = 0; i < words.length; i++) {
            if(wordsMap.containsKey(words[i])){
                wordsMap.get(words[i])[0] = wordsMap.get(words[i])[0]+1;
            }else {
                wordsMap.put(words[i],new int[]{1,0});
            }
        }//O(l)

        for (int i = 0; i < s.length()-wordLength*words.length+1; i++) {//O(n- w*m) l=word数组len
            String temp = s.substring(i, i + wordLength);
            if (wordsMap.containsKey(temp) && s.length()-i>=wordLength*words.length) {//包含数组元素且剩余长度大于等于 数组中字符总长度
                for (int j = i; j < s.length()-wordLength+1; j+=wordLength) {//O(m)
                    String str = s.substring(j, j + wordLength);
                    if (wordsMap.containsKey(str)) {
                        int sum = wordsMap.get(str)[0];
                        int cur = wordsMap.get(str)[1];

                        if (cur + 1 > sum)
                            break;
                        else
                            wordsMap.get(str)[1] = cur + 1;
                    }else{
                        break;
                    }
                }

                boolean flag = true;
                Iterator<String> iterator = wordsMap.keySet().iterator();
                while (iterator.hasNext()) {//o(l)
                    int[] tempCount = wordsMap.get(iterator.next());
                    if (tempCount[0] != tempCount[1]) {
                        flag = false;
                    }
                    tempCount[1] = 0;//复原
                }
                if (flag) {
                    res.add(i);
                    i+=wordLength-1;
                }

            }
        }

        return res;

    }
}

复杂度分析

时间复杂度：O(nm) //m代表word数组长度，n代表字符串s长度。 O(l)+O(n- wm)O(m)+o(l) 近似于O(mn)
空间复杂度：O(n) //n为保存word数组的哈希表大小

[chakochako]

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        allwords = Counter(words)
        wordnum = len(words)
        wordlen = len(words[0])
        res = []

        for i in range(len(s) - wordnum * wordlen + 1):
            index = i
            curwords = defaultdict(int)
            while index < i + wordnum * wordlen:
                currentword = s[index: index + wordlen]
                if  not currentword in allwords or curwords[currentword] == allwords[currentword]:
                    break
                curwords[currentword] += 1
                index = index + wordlen
            if index == i + wordnum * wordlen:
                res.append(i)
        return res

[zol013]

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        wordlen = len(words[0])
        substrlen = wordlen * len(words)
        ans = []
        count_1 = Counter(words)

        for i in range(0, len(s) - substrlen + 1):
            substr = s[i: i+substrlen]
            word_list = []
            for j in range(0, substrlen, wordlen):
                word_list.append(substr[j:j + wordlen])

            count_2 = Counter(word_list)
            if count_1 == count_2:
                ans.append(i)

        return ans

[LinnSky]

代码

   var findSubstring = function(s, words) {
     let left = 0, right = 0,
     slen = s.length,
     wordLen = words[0].length,
     wordNum = words.length
     let wlen = wordNum * wordLen
     let wordMap = new Map()
     for(let word of words) {
        let count = wordMap.has(word) ? wordMap.get(word) : 0
        wordMap.set(word, count + 1)
     }
    let res = []
    while(right < slen) {
        right++
        if(right - left === wlen) {
            if(match(s.substring(left, right), wordMap, wordNum, wordLen)) {
                res.push(left)
            }
            left++
        }
    }
    return res
  };

  function match(str, wordMap, wordNum, wordLen) {
    let map = new Map()
    for(let i = 0; i < wordNum; i++) {
        let word = str.substring(i * wordLen, (i + 1) * wordLen)
        let count = map.has(word) ? map.get(word) : 0
        map.set(word, count + 1)
    }
    let matchflag = true
    for(let [key, value] of wordMap) {
        if(!map.has(key) || map.get(key) !== value) {
            matchflag = false
        }
    }
    return matchflag
  }

[suukii]

Link to LeetCode Problem

S1: 滑动窗口+哈希表

naive 的想法是，将 words 里面的单词组合成字符串，然后到 s 里面去找有没有跟它一样的子串。但这样子时间复杂度太高了，因为 words 的组合有 words.length! 种，总复杂度差不多就是 s.length * words.length! 了。

那我们反过来想，s 的子串最多只有 s.length 个，我们只要判断 s 的每个子串是不是刚好由 words 数组里面的所有单词组成的就可以了。所以说，如果子串是刚好匹配 words 的单词的话，说明子串和 words 组成的字符串是两种组合情况，虽然排序不同，但包含的单词种类和数量是一样的。

解决方法就很明显了：

1. 用哈希表来统计 words 里面的单词和出现次数
2. 开始遍历 s 的第一个子串，按单词长度截开分别去哈希表中进行查询（单词长度是固定的，这就比较简单了）
   1. 找到的话讲哈希表中对应单词的次数减一，消掉一个
   2. 找不到或者单词次数已经为 0 的话，说明当前子串不符合要求，可以淘汰了
   3. 如果子串遍历完后哈希表的所有单词数量也刚好都减到了 0，说明找到了符合要求的子串。（这里到判断可以有多种，比如在开始子串比较之前用一个 count 变量来进行计数，如果子串比较结束后 count 刚好等于 words 的长度，就说明找到了符合要求的子串）
3. 对 s 的所有子串进行步骤 2 的处理

https://camo.githubusercontent.com/c8a6141eb1b4d86ec077ec7ad6bd2a74085cf614c97fbeed6b58d31eb95f270b/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f33305f302e706e67

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int wordLen = words[0].size(),
            substrLen = words.size() * wordLen,
            strLen = s.size();
        vector<int> res;
        unordered_map<string, int> wordMap;

        if (strLen < substrLen) return res;

        for (auto w : words)
            wordMap[w]++;

        for (int i = 0; i <= strLen - substrLen; i++) {
            unordered_map<string, int> strMap;
            for (int j = i; j <= i + substrLen - wordLen; j += wordLen) {
                strMap[s.substr(j, wordLen)]++;
            }
            if (wordMap == strMap) res.push_back(i);
        }
        return res;
    }
};

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    const wordLen = words[0].length;
    const substrLen = wordLen * words.length;
    const initialWordsMap = words.reduce((map, w) => {
        map[w] = (map[w] || 0) + 1;
        return map;
    }, {})
    const res = [];

    for (let i = 0; i <= s.length - substrLen; i++) {
        const wordsMap = {...initialWordsMap};
        for (let j = i; j < i + substrLen; j += wordLen) {
            const word = s.slice(j, j + wordLen);
            if (!(word in wordsMap) || wordsMap[word] == 0) break;
            wordsMap[word]--;
        }
        if (usedUpWords(wordsMap)) res.push(i);
    }
    return res;

    // ******************************************
    function usedUpWords(map) {
        return Object.values(map).every(n => n == 0);
    }
};

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
    const wordSize = words[0].length;
    const substringLen = wordSize * words.length;

    const wordsCount = {};
    words.forEach(w => (wordsCount[w] = (wordsCount[w] || 0) + 1));

    const res = [];
    for (let i = 0; i <= s.length - substringLen; i++) {
        const tempCount = { ...wordsCount };
        let count = words.length;

        for (let j = i; j < i + substringLen; j += wordSize) {
            const word = s.slice(j, j + wordSize);

            if (!(word in tempCount) || tempCount[word] <= 0) break;

            tempCount[word]--;
            count--;
        }

        if (count === 0) res.push(i);
    }
    return res;
};

• Time: $O((n-k)*k)$，n 是字符串 s 的长度，k 是单词的长度。
• Space: $O(m)$，m 是 words 数组的长度，哈希表的空间。

[rzhao010]

Thoughts

1. use one HasdhMap for checking the word shown in s, another hashMap to check in the sliding window
2. window size is the size of word, so each time we grab a word from s, first check if it's in the first map, if not, exit
3. if yes, we count the word in the second map, after the move, we compare if we have more counts in the second map than the first one for the same word, if yes, window start from the new word

Code

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        Map<String, Integer> wordMap = new HashMap<>();
        if (s.length() == 0 || words.length == 0) return res;

        for (String word: words) {
            // if the word doesn't exist in s, exit
            if (s.indexOf(word) < 0) {
                return res;
            }
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }
        // calculating word length
        int oneLen = words[0].length();
        int wordsLen = oneLen * words.length;
        if (wordsLen > s.length()) {
            return res;
        }
        // each time check one word
        // using two pointers as slide window
        for (int i = 0; i < oneLen; i++) {
            int left = i, right = i, count = 0;
            Map<String, Integer> subWord = new HashMap<>();
            while (right + oneLen <= s.length()) {
                String word = s.substring(right, right + oneLen);
                right += oneLen;
                if (!wordMap.containsKey(word)) {
                    // startover from the next word
                    left = right;
                    subWord.clear();
                    count = 0;
                } else {
                    // count the word
                    subWord.put(word, subWord.getOrDefault(word, 0) + 1);
                    ++count;
                    while (subWord.getOrDefault(word, 0) > wordMap.getOrDefault(word, 0)) {
                        // need to remove this word and start from the next word
                        String w = s.substring(left, left + oneLen);
                        subWord.put(w, subWord.getOrDefault(w, 0) - 1);
                        --count;
                        left += oneLen;
                    }
                    if (count == words.length) {
                        res.add(left);
                    }
                }

            }
        }
        return res;
    }
}

Complexity

• Time: O(n), only visit once
• Space: O(n)

[guoling0019]

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;
        HashMap<String, Integer> map = new HashMap<>();
        int one_word = words[0].length();
        int word_num = words.length;
        int all_len = one_word * word_num;
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < one_word; i++) {
            int left = i, right = i, count = 0;
            HashMap<String, Integer> tmp_map = new HashMap<>();
            while (right + one_word <= s.length()) {
                String w = s.substring(right, right + one_word);
                right += one_word;
                if (!map.containsKey(w)) {
                    count = 0;
                    left = right;
                    tmp_map.clear();
                } else {
                    tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
                    count++;
                    while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)) {
                        String t_w = s.substring(left, left + one_word);
                        count--;
                        tmp_map.put(t_w, tmp_map.getOrDefault(t_w, 0) - 1);
                        left += one_word;
                    }
                    if (count == word_num) res.add(left);
                }
            }
        }
        return res;
    }
}

[q815101630]

• Define number of words, length of each word
• Assign each word with a unique id and counts their frequency by a dictionary {id: freq}
• define window_size to be wordNum * wordLen

• for i in range(0, len(s)-window_size+1):

  • Define a subWords dictionary to check 1) if current word is allowed,2) if current word can be added, keep this while until the i+window_size is met

  • if idx == i+ window_size: res.append(i) then we can append i into res

    class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
    allwords = defaultdict(int)
    wordNum = len(words)
    wordLen = len(words[0])
    
    wordMap = {}
    myid = 0
    for i,v in enumerate(words):
        if v not in wordMap:
            wordMap[v] = myid
            myid+=1
        allwords[wordMap[v]] += 1
    
    window_size = wordNum*wordLen
    res = []
    
    for i in range(len(s)-window_size+1):
        subWords = collections.defaultdict(int)
        idx = i
    
        while idx < i+window_size:
            curWord = s[idx:idx+wordLen]
            if curWord not in wordMap or subWords[wordMap[curWord]] == allwords[wordMap[curWord]]:
                break
    
            subWords[wordMap[curWord]] += 1
            idx += wordLen
        if idx == i+ window_size:
            res.append(i)
    
    return res 

    Time: wordNum: N, wordLen: L, len(s): S N*L*(S-NL+1) => NLS-(NL)^2+NL => O(NLS) Space: O(N)