leetcode-pp / 91alg-7-daily-check

6 stars 0 forks source link

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

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

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"] 输出：[]

XXjo commented 2 years ago

思路

1、使用wordMap保存单词以及对应的数目，key为单词，value为单词对应的数目
2、使用left和right构成定长的滑动窗口，在滑动窗口中截取字串subStr。如果subStr不存在于wordMap中，left左移；若subStr存在于wordMap中，则存入tempMap。如果tempMap[subStr] > wordMap[subStr]，left左移
3、最后判断tempMap和wordMap是否相同

代码

var findSubstring = function(s, words) {
    let res = [];
    if(words.length === 0) return res;
    let wordLength = words[0].length;

    //wordMap：统计words中的单词数目
    let wordMap = new Map();
    for(let word of words){
        let count = wordMap.has(word) ? wordMap.get(word) : 0;
        wordMap.set(word, count + 1);
    }

    let tempMap = new Map();
    for(let left = 0; left < s.length - wordLength * words.length + 1; left++){
        let right = left + wordLength * words.length - 1;
        let i = left;
        while( i <= right){
            let subStr = s.slice(i, i + wordLength);
            if(wordMap.has(subStr)){
                let tempCount = tempMap.has(subStr) ? tempMap.get(subStr) : 0;
                tempMap.set(subStr, tempCount + 1);
                if(tempMap.get(subStr) > wordMap.get(subStr)) break;
                i += wordLength;
            }
            else break;
        }
        if(i - right === 1) {
            res.push(left);
        }
        tempMap.clear();
    }
    return res;
};

复杂度分析

时间复杂度:O(n * m) n表示s长度，m表示单词个数
空间复杂度:O(m) m表示单词个数

maybetoffee commented 2 years ago

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();

        int wordNum = words.length;
        if(wordNum == 0) return res;
        int wordLen = words[0].length();
        //first map to store the target word and count
        Map<String, Integer> mapTarget = new HashMap<>();
        for(String word : words){
            mapTarget.put(word, mapTarget.getOrDefault(word, 0)+1);
        }

        //traverse all the subStrings in s

        for(int i = 0; i < s.length()-wordNum*wordLen+1; i++){
            Map<String, Integer> mapCurr = new HashMap<>();
            int num = 0;
            while(num < wordNum){
                String word = s.substring(i+wordLen*num, i+wordLen*(num+1));
                if(mapTarget.containsKey(word)){
                    mapCurr.put(word, mapCurr.getOrDefault(word,0)+1);
                    if(mapCurr.get(word) > mapTarget.get(word)){
                        break;
                    }
                }else{
                    break;
                }
                num++;
            }
            if(num == wordNum){
                res.add(i);
            }
        }
        return res;
    }
}

AConcert commented 2 years ago

var findSubstring = function(s, words) {
    let correct = {};
    for (let i = 0 ; i < words.length; i++) {
        correct[words[i]] = correct[words[i]] || 0;
        correct[words[i]] ++;
    }

    let ret = [];

    for (let start = 0; start < words[0].length; start ++) {
        let map = {};
        let len = words[0].length;
        for (let i = start; i < s.length;) {
            if (i + len > s.length) break;

            let tmp = s.slice(i, i + len);
            map[tmp] = map[tmp] || 0;
            map[tmp] ++;

            if (i - len * words.length >= 0) {
                let prev = s.slice(i - len * words.length, i - len * words.length + len);
                map[prev] = map[prev] || 0;
                map[prev] --;
            }

            let flag = true;
            for (let key in correct) {
                if (correct[key] !== map[key]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ret.push(i - (words.length - 1) * len);
            }
            i = i + len;
        }
    }

    return ret;
};

mo660 commented 2 years ago

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if (words.size() == 0)
            return res;
        int wlen = words[0].size();
        int slen = s.size();
        int count = words.size();
        map<string, int>mp;
        for(auto it : words)
            mp[it]++;

        for (int i=0;i<slen-(wlen*count)+1;i++){
            string cur=s.substr(i,wlen*count);
            map<string,int>tmp;
            int j=0;
            for (;j<cur.length();j+=wlen){
                string word = cur.substr(j,wlen);
                if (0 == mp.count(word))
                    break;
                tmp[word]++;
                if(tmp[word] > mp[word]){
                    break;
                }
            }
            if(j == cur.length())
                res.push_back(i);
        }
        return res;
    }
};

wychmod commented 2 years ago

思路

两个哈希表来控制，在遍历words数组填满第一个哈希表，在遍历字符串的过程中填满第二个哈希表，然后判断两个哈希表是否相等。

代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n = len(words[0])
        ans = []
        dic = {}
        for i, word in enumerate(words):
            dic[word] = dic.get(word, 0) + 1

        for i in range(len(s)-n*len(words)+1):
            tmp = {}
            for j in range(len(words)):
                char = s[i + j * n:i + n + j * n]
                if dic.get(char, -1) == -1:
                    break
                tmp[char] = tmp.get(char, 0) + 1
                if tmp.get(char) > dic.get(char):
                    break
            if tmp == dic:
                ans.append(i)
        return ans

复杂度

时间复杂度 On*m 空间复杂度 Om

bzlff commented 2 years ago

思路

使用两个哈希表

代码


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        from collections import Counter

        if not s or not words: return []
        word_len = len(words[0])
        all_len = len(words) * word_len
        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, word_len):
                c_tmp.append(tmp[j: j+word_len])

            if Counter(c_tmp) == words:
                res.append(i)
        return res

biscuit279 commented 2 years ago

思路

滑动窗口

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

时间复杂度：O(s) 空间复杂度：O(mnk)

ha0cheng commented 2 years ago

思路：双指针+哈希表先用哈希表存储需要匹配的字符列表的统计个数。用双指针中间的窗口来代表目前访问的字符串，用哈希表来代表目前这段窗口的统计个数，如果一致则记录，不一致则分情况移动左右指针，具体的是： 1.如果右指针之前指的字符在字符列表中，统计个数超过了原有，那么就找到可以减去这个字符串个数的位置，移动左节点 2.如果不在列表中，则移动右指针+1，左指针指向离右指针距离为一个匹配字符串的长度，重新记录哈希表。

复杂度分析：时间复杂度：O(n+m), n是字符串长度，m是字符列表长度，因为遍历一遍字符串，每次需要操作O(1) 空间复杂度：O(m)，哈希表的大小与m成正比

代码如下

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        length = len(words[0])
        Count = Counter()
        curr = {}
        for i in range(len(words)):
            Count[words[i]] +=1
        n = i+1
        r = []
        left = 0
        right = length
        C = Counter()
        while right < len(s)+1:
            if Count[s[right-length:right]]:

                C[s[right-length:right]] +=1
                print(left,right)
                if C[s[right-length:right]]>Count[s[right-length:right]]:
                    C[s[left:left+length]] -=1
                    left +=length
                    while C[s[right-length:right]]>Count[s[right-length:right]]:
                        C[s[left:left+length]] -=1
                        left +=length
                    right+=length

                else:
                    # print(left,right)  
                    if (right - left)/length == n:
                        r.append(left)
                        C[s[left:left+length]] -=1
                        left+=length
                    right+=length 

            else:
                right+=1
                left = right - length
                C = Counter()

        return r

KWDFW commented 2 years ago

Day23

30、串联所有单词的子串

javascript #哈希表 #双指针

思路

1、建立一个滑动窗口，遍历s

2、建立两个哈希表分别记录滑动窗口和words中的数据

3、窗口和words中数据满足题意时，记录位置

4、返回记录位置的数组

题解

代码

var findSubstring = function(s, words) {
    const wordsLength=words.length,wordLength=words[0].length
    let mapWords={}//建立记录words数据的哈希表
    for(let n of words){
        mapWords[n]=(mapWords[n]||0)+1
    }//将words数据记录到哈希表中
    let i=0,l=0,r=0,res=[],win={},count=0
    while(i<wordLength){
        //当s开头字符不是words中单词的首字符时，可以多次遍历得出结果
        l=i,r=i,win={},count=0//每次遍历将变量置空
        while(r<s.length){//按每个单词来遍历s
            const ss=s.substring(r,r+wordLength)
            //获取下一个单词
            r+=wordLength
            //窗口向右滑动一格
            if(!mapWords[ss]){
                //如果获取到不在words中的单词，就清空原窗口，重新建立窗口
                l=r
                win={}
                count=0
            }else{
                win[ss]=(win[ss]||0)+1//将新单词加入到窗口中
                count++//出现在words中的单词的个数
                while(win[ss]>mapWords[ss]){
                    //出现多余单词，就把窗口从左侧收缩
                    const sl = s.substring(l,l+wordLength)
                    win[sl] = (win[sl]||0)-1
                    count--
                    l+=wordLength
                }
                if(count===wordsLength) res.push(l)
            }
        }
        i++
    }
    return res
};

复杂度分析

时间复杂度：O(n2)

空间复杂度：O(n)

ViviXu-qiqi commented 2 years ago

var findSubstring = function(s, words) {
    let totalCharCount = 0
    let map = new Map()

    let wordLength = words[0].length
    let wordCount = words.length

    let slideWindow = wordLength * wordCount

    for (let word of words) {
        map.has(word) ? map.set(word, map.get(word) + 1) : map.set(word, 1)
    }

    let leftIndex = 0
    let rightIndex = slideWindow - 1
    let result = []

    const helper = (tempStr) => {
        let visited = new Map()

        for (let i = 0; i < tempStr.length; i+= wordLength) {
            let word = tempStr.substr(i, wordLength)

            visited.has(word) ? visited.set(word, visited.get(word) + 1) : visited.set(word, 1)
        }

        for (let [key, val] of visited) {
            if (map.get(key) != val) return false
        }

        return true
    }

    while (rightIndex < s.length) {

        if (rightIndex - leftIndex + 1 == slideWindow) {
            let tempStr = s.substring(leftIndex, rightIndex + 1)

            if (helper(tempStr)) result.push(leftIndex)

            leftIndex++
        }

        rightIndex++
    }

    return result
};

zhishinaigai commented 2 years ago

代码

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; // 子串 不在 words 里面
                if (++sub[word] > search[word]) break; // 子串个数 比 words 多
            }
            if (j == m) res.push_back(i); // 完全匹配
        }
        return res;
    }
};

duke-github commented 2 years ago

思路

滑动窗口 每次从s上截取数组中所有word总长度的字符串 从截取的字符串上再截取一个个word长度的字符串 使用map判断所有的字符是否都存在且次数一样 一样 则将下表记录到ans中

复杂度

时间复杂度：O(n*m) 空间复杂度：O(n*n)

代码

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        Map<String, Integer> keyValue = new HashMap<>();
        for (String word : words) {
            keyValue.put(word, keyValue.getOrDefault(word, 0) + 1);
        }
        int lenOfWord = words[0].length();
        int lenOfAllWords = lenOfWord * words.length;
        for (int i = 0; i < s.length() - lenOfAllWords + 1; i++) {
            String temp = s.substring(i, i + lenOfAllWords);
            Map<String, Integer> tempMap = new HashMap<>();
            for (int j = 0; j < lenOfAllWords; j += lenOfWord) {
                String tempj = temp.substring(j, j + lenOfWord);
                if (!keyValue.containsKey(tempj) || keyValue.get(tempj) <= tempMap.getOrDefault(tempj,0)) {
                    break;
                }
                tempMap.put(tempj, tempMap.getOrDefault(tempj, 0) + 1);
            }
            if (tempMap.equals(keyValue)) {
                ans.add(i);
            }
        }
        return ans;
    }

linjunhe commented 2 years ago

思路

以words中每个单词为key，出现次数为value，存入hashtable
滑动窗口大小固定为wordLen * wordNum，每次滑动一格
每次滑动，比较窗口中的单词的出现次数和需要的出现次数是否相同

Code

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        strLen = len(s)
        wordNum = len(words)
        wordLen = len(words[0])
        windowSize = wordNum * wordLen

        init = {word:0 for word in words}
        need = init.copy()
        for word in words:
            need[word] += 1

        start = 0
        ans = []

        while start < strLen - windowSize + 1:
            cnt = init.copy()
            for i in range(start, start + windowSize, wordLen):
                word = s[i: i + wordLen]
                if word not in cnt:
                    break
                else:
                    cnt[word] += 1
                    if cnt[word] > need[word]:
                        break
            else: 
                ans.append(start)

            start += 1

        return(ans)

复杂度分析

时间复杂度：O((strLen-windowSize)*windowSize)
空间复杂度：O(windowSize)

taojin1992 commented 2 years ago

/*
Time:
O(words.length()) + O(s.length() - unitLen*wordNum) * [O(unitLen*wordNum) + O(wordNum) * O(unitLen)]
-> O(s.length() - unitLen*wordNum) * O(wordNum) * O(unitLen)

Space:two maps
O(number of unique words)

*/

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> indices = new ArrayList<>();
        // get freq 
        Map<String, Integer> wordFreq = new HashMap<>();
        for (String word : words) {
            wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);
        }

        int unitLen = words[0].length(), wordNum = words.length;
        // sliding window
        // len to check = word.length * num of words
        // index to check: [0, end], s.length()-1 - end + 1=word.length * num of words
        // end = s.length() - unitLen*wordNum

        for (int start = 0; start <= s.length() - unitLen*wordNum; start++) {
            String curSub = s.substring(start, start + unitLen*wordNum);
            // use a curFreqMap to see the difference
            Map<String, Integer> curWordFreq = new HashMap<>();
            int wordIndex = 0;
            // within curSub
            for (wordIndex = 0; wordIndex + unitLen <= curSub.length(); wordIndex += unitLen) { // note the incremental
                String curUnit = curSub.substring(wordIndex, wordIndex + unitLen);
                // not in given dictionary
                if (!wordFreq.containsKey(curUnit)) {
                    break;
                }
                curWordFreq.put(curUnit, curWordFreq.getOrDefault(curUnit, 0) + 1);
                // > required freq
                if (curWordFreq.get(curUnit) > wordFreq.get(curUnit)) {
                    break;
                }
            }

            // if finish the check, bingo
            if (wordIndex == curSub.length()) {
                indices.add(start);
            }

        }

        return indices;
    }
}

liuajingliu commented 2 years ago

解题思路

哈希表 + 滑动窗口

代码实现

javaScript

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    let hashMap = new Map;
    const wordLength = words[0].length;
    const result = [];
    for (const word of words){
        const val = (hashMap.get(word) || 0) +  1
        hashMap.set(word, val);
    }
    for(let i = 0; i <= s.length - wordLength * words.length; i++){
        const temp = new Map(hashMap);
        let wordLeft = words.length;
        for(let j = i; j < i + wordLength * words.length; j+= wordLength){
            const curWord = s.slice(j, j+ wordLength);
            if (!temp.has(curWord) || temp.get(curWord) <= 0) {
                break;
            }
            wordLeft --;
            temp.set(curWord, temp.get(curWord) - 1);
        }
        if (wordLeft === 0) {
            result.push(i)
        }
    }

    return result;
};

复杂度分析

时间复杂度 $O(NM)$ 其中 N是输入String的长度，M是words的长度
空间复杂度 $O(M)

bigboom666 commented 2 years ago

思路

滑动窗口

code

class Solution {
    //滑动窗口
    //滑动窗口的窗长：数组中字串的长度和
    //针对一个窗口内的字串，以word的长度分割。分割出的字串如果和word数组里的完全匹配则找到一个index
    public List<Integer> findSubstring(String s, String[] words) {
        int windowLength = words.length * words[0].length() ;
        List<String> list = new ArrayList<>(Arrays.asList(words));
        //System.out.println("list: " + list);
        List<Integer> result  = new ArrayList<Integer>();
        for(int index = 0; (index + windowLength) <= s.length(); index++){
            for(int i = 0 ;i<words.length;i++){
                int start = index + i*words[0].length();
                int end = index + i*words[0].length() + words[0].length();
                String temp = s.substring(start, end);
                //System.out.println("["+start+","+end+"), : " + temp);
                if(!list.remove(temp)){
                    //System.out.println("not contain,break! ");
                    break;
                }
            }
            if(list.isEmpty()){
                result.add(index);
            }
            list.clear();
            list.addAll(Arrays.asList(words));
        }
        return result;
    }
}

复杂度

时间：O(N*M)
空间：O(M)
M为wrod数组长度

houyanlu commented 2 years ago

思路

其实还是暴力法去判断每一个连续子串是否符合要求，在比较的过程中使用了两个hash表来比较是否子串中word的个数是相等的

代码


class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int length   = s.length();
        int wordSize = words[0].length();
        vector<int> ansVec;

        unordered_map<string, int> targetMap;
        for (const auto& word : words) {
            ++targetMap[word];
        }

        for (int i = 0; i < length - wordSize * words.size() + 1; i++) {
            string subString = s.substr(i, wordSize * words.size());
            unordered_map<string, int> tmpMap;
            int j = 0;
            for ( ; j < subString.length(); j = j + wordSize) {
                string tmpStr = subString.substr(j, wordSize);
                if (targetMap.count(tmpStr) < 0) {
                    break;
                }

                ++tmpMap[tmpStr];

                if (tmpMap[tmpStr] > targetMap[tmpStr]) {
                    break;
                }
            } 

            if (j == subString.length()) {
                ansVec.push_back(i);
            }
        }

        return ansVec;
    }
};

复杂度分析 令 length 为字符串 S 长度, m 为 words 数组元素个数, k 为单个 word 字串长度

时间复杂度：O(length m k), 就是两重for循环的时间复杂度
空间复杂度：O(m) 哈希表的大小就是words数组元素的个数，多少个key也就是

flyzenr commented 2 years ago

思路
- 涉及出现次数，要用哈希表
- 涉及子串，考虑滑动窗口
  - 设置两个指针，表示滑动窗口的左边界和有边界
  - 如果当前字符不在子串里，滑动右指针
  - 因为单词长度固定的，我们可以计算出截取字符串的单词个数是否和 words 里相等，所以我们可以借用哈希表。
  - 一个是哈希表是 words，一个哈希表是截取的字符串，比较两个哈希是否相等！

Code - 滑动窗口+哈希表比较

      class Solution:
          def findSubstring(self, s: str, words: List[str]) -> List[int]:
              from collections import Counter
              # 主串s中没有这个单词，直接返回空
              if not s or not words:return []  
              # 每个单词的长度， words总长度
              one_word = len(words[0])
              word_num = len(words)
              n = len(s)
              # 主串s长度小于单词总和，返回空
              if n < one_word:return []
              words = Counter(words)
              res = []
              # 只讨论从0，1，...， one_word-1 开始的子串情况，
              # 每次进行匹配的窗口大小为 word_num，每次后移一个单词长度，由左右窗口维持当前窗口位置
              for i in range(0, one_word):
                  cur_cnt = 0
                  #  设置左右窗口
                  left = i
                  right = i
                  # 统计每个符合要求的word
                  cur_Counter = Counter()
                  # 右窗口不能超出主串长度
                  while right + one_word <= n:
                      # 得到一个单词
                      w = s[right:right + one_word]
                      # 右窗口往右移动一个单词的长度 word_num
                      right += one_word
                      # 判断如果words中没有这个单词，那么当前窗口肯定匹配失败，左指针直接右移到这个单词后面
                      if w not in words:
                          left = right
                          # 窗口内单词统计map清空，重新统计
                          cur_Counter.clear()
                          # 符合要求的单词数清0
                          cur_cnt = 0
                      else:
                          # 统计当前子串中这个单词出现的次数
                          cur_Counter[w] += 1
                          cur_cnt += 1
                          # 如果这个单词出现的次数大于words[]中它对应的次数，又由于每次匹配和words长度相等的子串
                          # 如 ["foo","bar","foo","the"]  "| foobarfoobar| foothe"
                          # 第二个bar虽然是words[]中的单词，但是次数超了，那么右移一个单词长度后 "|barfoobarfoo|the"
                          # bar还是不符合，所以直接从这个不符合的bar之后开始匹配，
                          # 也就是将这个不符合的bar和它之前的单词(串)全移出去
                          while cur_Counter[w] > words[w]:
                              # 从当前窗口字符统计map中删除从左窗口开始到数量超限的所有单词(次数减一)
                              left_w = s[left:left+one_word]
                              # 左窗口位置右移一个单词长度
                              left += one_word
                              # 符合的单词数减一
                              cur_Counter[left_w] -= 1
                              cur_cnt -= 1
                          # 当前窗口字符串满足要求
                          if cur_cnt == word_num :
                              res.append(left)
              return res

复杂度
- 滑动窗口
  - 时间复杂度: $O(n)$ ，字符串的长度
  - 空间复杂度 $O(n)$

dzwhh commented 2 years ago

【Day 23】30.Substring with Concatenation of All Words「串联所有单词的子串」

题目地址: 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"] 输出：[]

示例 3

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12]

前置知识

哈希表
双指针
js 版本

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    let correct = {};
    for (let i = 0 ; i < words.length; i++) {
        correct[words[i]] = correct[words[i]] || 0;
        correct[words[i]] ++;
    }

    let ret = [];

    for (let start = 0; start < words[0].length; start ++) {
        let map = {};
        let len = words[0].length;
        for (let i = start; i < s.length;) {
            if (i + len > s.length) break;

            let tmp = s.slice(i, i + len);
            map[tmp] = map[tmp] || 0;
            map[tmp] ++;

            if (i - len * words.length >= 0) {
                let prev = s.slice(i - len * words.length, i - len * words.length + len);
                map[prev] = map[prev] || 0;
                map[prev] --;
            }

            let flag = true;
            for (let key in correct) {
                if (correct[key] !== map[key]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ret.push(i - (words.length - 1) * len);
            }
            i = i + len;
        }
    }

    return ret;
};

maggiexie00 commented 2 years ago

def findSubstring(self, s: str, words: List[str]) -> List[int]:
    from collections import Counter
    if not s or not words:return []
    all_len = sum(map(len, words))
    n = len(s)
    words = Counter(words)
    res = []
    for i in range(0, n - all_len + 1):
        tmp = s[i:i+all_len]
        flag = True
        for key in words:
            if words[key] != tmp.count(key):
                flag = False
                break
        if flag:res.append(i)
    return res

guangsizhongbin commented 2 years ago

func findSubstring(s string, words []string) []int { wL := len(words) // words 中单词个数 oneWordL := len(words[0]) // 每个单词长度 hm := make(map[string]int) // 存words中单词的map Allcount := 0 // 记录不同单词的个数，用于在窗口滑动过程中判断是否满足答案条件 for i := 0; i < wL; i++ { if _, ok := hm[words[i]]; !ok { Allcount++ } hm[words[i]]++ }

ans := []int{}
for i := 0; i < oneWordL; i++ {
    Count := 0
    tmpHm := map[string]int{} // 滑动窗口中的单词记录map
    left, right := i, i + oneWordL
    for ; right <= len(s); right += oneWordL {
        str := s[right - oneWordL : right]
        if _ , ok := hm[str]; ok {
            tmpHm[str]++
            if tmpHm[str] == hm[str] {
                Count++
            }
        }

        for right - left > oneWordL * wL {
            str := s[left : left + oneWordL]
            if _, ok := tmpHm[str]; ok {
                tmpHm[str]--
            }

            if tmpHm[str] + 1 == hm[str] {
                Count--
            }
            left += oneWordL
        }

        if Count == Allcount && right - left == oneWordL * wL { // 两个条件判断是否
            ans = append(ans, left)
        }
    }
}
return ans

}

xil324 commented 2 years ago

··· class Solution(object): def findSubstring(self, s, words): """ :type s: str :type words: List[str] :rtype: List[int] """ n = len (s); k = len (words); word_length = len(words[0]); substring_size = k * word_length; counter = collections.Counter(words);

hexlper function to determine whether starting index i can find a valid substring

    def helper(start):
        copy = counter.copy(); 
        used = 0;
        for j in range(start, start+substring_size, word_length):
            str = s[j:j+word_length];
            if copy[str] > 0: 
                copy[str] -= 1;
                used += 1;
            else:
                break;
        return used == k; 

    res = []; 
    for i in range(n-substring_size+1):
        if helper(i):
            res.append(i);
    return res;

···

time complexity: for helper, creating a hash table needs O(k) and needs to check k word_length times (b). the total time complexity for helper is O(k+kb) => O(k b); overal, we need to call the hleper function for n - kb time => O(nkb-(k*b)^2);

#space complexity: O(K+b)

HuiWang1020 commented 2 years ago

Idea

HashMap + Sliding window

two maps. one for word count in Words array, one for word count in current window. check the word and frequency in two maps.
sliding window. traverse the string (word.length times) expand or shrink the window by cuurent word count

Code

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 wordLen = words.length;
        int unitLen = words[0].length();
        //word count
        Map<String, Integer> allWords = new HashMap<>();
        for (String str : words) {
            allWords.put(str, allWords.getOrDefault(str, 0) + 1);
        }

        //tranverse all start points
        for (int i = 0; i < unitLen; i++) {
            //two pointer
            int left = i, right = i;
            Map<String, Integer> hasWords = new HashMap<>();
            int count = 0;
            while(right <= s.length() - unitLen) {
                String cur = s.substring(right, right + unitLen);
                right += unitLen;
                hasWords.put(cur, hasWords.getOrDefault(cur, 0) + 1);
                if(allWords.containsKey(cur)) {
                    count++;
                    while (allWords.get(cur) < hasWords.get(cur)) {
                        //shrink window
                        String remove = s.substring(left, left + unitLen);
                        hasWords.put(remove, hasWords.get(remove) - 1);
                        count--;
                        left += unitLen;
                    }
                } else {   
                    //clear map/ start a new window/reset left pointer and count
                    hasWords.clear();
                    left = right;
                    count = 0;
                }
                //check result every time
                if(count == wordLen) {
                    res.add(left);
                }
            }

        }
        return res;
    }
}

Complexity time=o(n*m) space=o(m)

1973719588 commented 2 years ago

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

时间复杂度：O(N*M) 空间复杂度：O(N)

ZETAVI commented 2 years ago

public List findSubstring(String s, String[] words) { ArrayList ans = new ArrayList<>(); HashMap<String, Integer> wordsMap = new HashMap<>(); for (String word:words){ wordsMap.put(word,wordsMap.getOrDefault(word,0)+1); }

    int len = s.length();
    int step = words[0].length();
    int nums = words.length;
    for (int i = 0; i <= len - step * nums; i++) {
        HashMap<String,Integer> count = new HashMap<>();
        boolean flag=true;
        for (int j = 0; j < nums; j++) {
            int start = i + j * step;
            String sub = s.substring(start, start + step);
            if (!wordsMap.containsKey(sub)){
                flag=false;
                break;
            }
            count.put(sub, count.getOrDefault(sub, 0) + 1);
            if (count.get(sub)>wordsMap.get(sub)){
                flag=false;
                break;
            }
        }
        if (flag)ans.add(i);
    }
    return ans;
}

Yongxi-Zhou commented 2 years ago

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

zhiyuanpeng commented 2 years ago

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        w = collections.Counter(words)
        step = len(words[0])
        steps = step*len(words)
        l, r = 0, 0
        ans = []
        # method 1
        # for r in range(steps, len(s)+1):
        #     w_s = collections.defaultdict(int)
        #     flag = 1
        #     for i in range(l, r, step):
        #         cur = s[i: i+step]
        #         w_s[cur] += 1
        #     if set(w_s.keys()) != set(w.keys()):
        #         flag = 0
        #     if flag:
        #         for val in w.keys():
        #             if w_s[val] != w[val]:
        #                 flag = 0
        #                 break
        #     if flag:
        #         ans.append(l)
        #     l += 1
        # return ans
        # method 2
        # for r in range(steps, len(s)+1):
        #     w_s = collections.defaultdict(int)
        #     for i in range(l, r, step):
        #         cur = s[i: i+step]
        #         w_s[cur] += 1
        #     if w_s == w:
        #         ans.append(l)
        #     l += 1
        # return ans
        # method 3
        for r in range(steps, len(s)+1):
            w_s = collections.defaultdict(int)
            for i in range(l, r, step):
                cur = s[i: i+step]
                if cur not in w:
                    break
                w_s[cur] += 1
                if w_s[cur] > w[cur]:
                    break
            if w_s == w:
                ans.append(l)
            l += 1
        return ans

time

leetcode-pp / 91alg-7-daily-check

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

30. 串联所有单词的子串

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度分析

思路

代码

复杂度

思路

代码

思路

javascript #哈希表 #双指针

思路

代码

复杂度分析

代码

思路

复杂度

代码

思路

Code

复杂度分析

解题思路

代码实现

复杂度分析

思路

code

复杂度

思路

代码

思路

涉及出现次数，要用哈希表

涉及子串，考虑滑动窗口

Code - 滑动窗口+哈希表比较

复杂度

滑动窗口

【Day 23】30.Substring with Concatenation of All Words「串联所有单词的子串」

题目描述

前置知识

hexlper function to determine whether starting index i can find a valid substring

time complexity: for helper, creating a hash table needs O(k) and needs to check k word_length times (b). the total time complexity for helper is O(k+kb) => O(k b); overal, we need to call the hleper function for n - kb time => O(nkb-(k*b)^2);

Idea

Code

iterate windows

当前window的可能，从i开始

收集当前cur的每个词的频率，如果跟counter不一样就剪枝