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

5 stars 0 forks source link

【Day 23 】2022-08-06 - 30. 串联所有单词的子串 #38

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

Hacker90 commented 2 years ago

from collections import Counter from collections import defaultdict c = Counter(words) m = len(words) n = len(words[0]) ret = [] total_length = m * n

    #Loop over word length
    for k in xrange(n):
        left = k
        subd = defaultdict(int)
        count = 0
        for j in xrange(k, len(s) - n + 1, n):
            word = s[j:j+n]
            if word in c:
                subd[word] += 1
                count += 1
                while subd[word] > c[word]:
                    subd[s[left:left+n]] -= 1
                    left += n
                    count -= 1
                if count == m:
                    ret.append(left)
            else:
                left = j + n
                subd = defaultdict(int)
                count = 0
    return ret

hx-code commented 2 years ago

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

};

zpc7 commented 2 years ago

思路

滑动窗口+hashMap

代码 TS

function findSubstring(s: string, words: string[]): number[] {
    const cnts = new Map<string, number>(), ans = new Array<number>(), n = words.length, step = words[0].length
    for (const word of words) {
        if (cnts.has(word)) {
            cnts.set(word, cnts.get(word) + 1)
        } else {
            cnts.set(word, 1)
        }
    }
    out:
    for (let i = 0; i <= s.length - step * n; i++) {
        const curCnts = new Map<string, number>()
        for (let j = 0; j < n; j++) {
            const subStr = s.substr(i + j * step, step)
            if (!cnts.has(subStr)) {
                continue out
            }
            if (curCnts.has(subStr)) {
                curCnts.set(subStr, curCnts.get(subStr) + 1)
                if (curCnts.get(subStr) > cnts.get(subStr)) {
                    continue out
                }
            } else {
                curCnts.set(subStr, 1)
            }
        }
        ans.push(i)
    }
    return ans
};

luhaoling commented 2 years ago

Idea

仅考虑遍历过程， 遍历 s 串的时间复杂度为 O(n - m + 1)O(n−m+1), 其中 n 为 s 字符串长度, m 为 words[0].length * words.length，也就是 words 的字符总数。问题关键在于如何判断 s 的子串 Y 是否可以由 words 数组的构成，由于 words 中单词长度固定，我们可以将 Y 拆分成对应 words[0]长度的一个个子串 parts, 只需要判断 words 和 parts 中的单词是否一一匹配即可，这里用两个哈希表表比对出现次数即可。一旦一个对应不上，意味着此种分割方法不正确，继续尝试下一种即可。

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

JohnxiZhao commented 2 years ago

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int n = s.length();
        int m = words.length; 
        int len = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        List<Integer> res = new ArrayList<>();
        out:for (int i = 0; i + m * len <= n; i++) {
            Map<String, Integer> cur = new HashMap<>();
            String str = s.substring(i, i + m * len);
            for (int j = 0; j < str.length(); j += len) {
                String item = str.substring(j, j + len);
                if (!map.containsKey(item)) continue out;
                cur.put(item, cur.getOrDefault(item, 0) + 1);
            }
            if (cur.equals(map)) res.add(i);
        }
        return res;
    }
}

ccslience commented 2 years ago

1.思路: 遍历 s 串中所有长度为 (words[0].length * words.length) 的子串 Y，查看 Y 是否可以由 words 数组构造生成;
1.思路: 由于 words 中单词长度固定，我们可以将 Y 拆分成对应 words[0]长度的一个个子串 parts, 只需要判断 words 和 parts 中的单词是否一一匹配即可;
2.时间复杂度:O(nm - mkm)((n - mk) m, 空间复杂度:O(m); (n:s的长度, m:words的长度, k:words[0]的长度).
1. 做题的时候没主要到word里面的词长度是相同的, 所以想复杂了.

class Solution
{
public:
vector<int> findSubstring(string s, vector<string>& words)
{
    for(auto i: words)
    {
        words_dict[i]++;
    }
    int single_len = words[0].length();
    int sub_len = single_len * words.size();
    int p = 0, q, flag;
    string sub_str;
    vector<int> res;

    while(p != s.length() - sub_len + 1)
    {
        flag = 1;
//            words_dict_copy.clear();
        words_dict_copy = words_dict;
        for(q = p + single_len - 1; q <=  p + sub_len - 1; q+=single_len)
        {
            sub_str = s.substr(q - single_len + 1, single_len);
            if(words_dict_copy.find(sub_str) == words_dict_copy.end())
            {
                flag = 0;
                break;
            }
            else
            {
                words_dict_copy[sub_str]--;
                if (words_dict_copy[sub_str] == 0)
                    words_dict_copy.erase(sub_str);
            }
        }
        if(flag)
            res.push_back(p);
        p++;
    }
    return res;

}
private:
unordered_map<string, int> words_dict;
unordered_map<string, int> words_dict_copy;
};

wsmmxmm commented 2 years ago

//刚想说，我也太聪明了吧，然后超出时间限制卒。 class Solution {

public List<Integer> findSubstring(String s, String[] words) {
    boolean[] booArr = new boolean[words.length];
    List<Integer> res = new ArrayList<Integer>();
    int len = words[0].length();
    Map<String, Integer> map = new HashMap<>();
    for(String word:words){
        int temp = map.getOrDefault(word, 0);
        map.put(word, temp + 1);
    }

    int r = 0;
    int l = 0;

    char[] c = s.toCharArray();

    while(l + len <= c.length){
        r = l + len * words.length - 1;
        if(isRes2(l, r, c, map,len,words)){
            res.add(l);
        }
        l++;

    }
    return res;

}
boolean isRes2(int l, int r, char[] c, Map<String, Integer> map2, int len, String[] words){
    Map<String, Integer> map = new HashMap<>();
    for(int i = l; i <= r; i += len){
        StringBuffer sb = new StringBuffer();
        int j = i;
        while(j < c.length && sb.length() < len){
            sb.append(c[j]);
            j++;
        }
        //System.out.println("sb=:"+sb.toString()+";l=:"+l);

        int temp = map.getOrDefault(sb.toString(), 0);
        map.put(sb.toString(), temp + 1);
    }

    for(String s: words){
        int temp1 = map.getOrDefault(s, 0);
        int temp2 = map2.getOrDefault(s, 0);
        if(temp1 == 0 || temp1 != temp2){
            return false;
        }
    }
    return true;
}

}

wzasd commented 2 years ago

代码

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

wengzhouyunfan commented 2 years ago

// for every possible ending index we want to find every valid index such that subString [end - allwordlen + 1, end] is valid
class Solution {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if(words == null || words.length == 0 || s.length() == 0) return res;
        int wordLen = words[0].length();
        int numWord = words.length;
        int windowLen = wordLen * numWord;
        int sLen = s.length();
        HashMap<String, Integer> map = new HashMap<>();
        for(String word : words) map.put(word, map.getOrDefault(word, 0) + 1);

        for(int i = 0; i < wordLen; i++) {  
            HashMap<String, Integer> curMap = new HashMap<>();
            for(int j = i, count = 0, start = i; j + wordLen <= sLen; j += wordLen) {  
                if(start + windowLen > sLen) break;
                String word = s.substring(j, j + wordLen);
                if(!map.containsKey(word)) {
                    curMap.clear();
                    count = 0;
                    start = j + wordLen;
                }
                else {
                    if(j == start + windowLen) { 
                        String preWord = s.substring(start, start + wordLen);
                        start += wordLen;
                        int val = curMap.get(preWord);
                        if(val == 1) curMap.remove(preWord);
                        else curMap.put(preWord, val - 1);
                        if(val - 1 >= map.get(preWord)) count--;  
                    }

                    curMap.put(word, curMap.getOrDefault(word, 0) + 1);
                    if(curMap.get(word) > map.get(word)) count++;  
                    if(count == 0 && start + windowLen == j + wordLen) {
                        res.add(start);
                    }
                }
            }
        }
        return res;
    }
}
T:O(sLen * wordLen)
S:O(wordLen * wordNum)

maoting commented 2 years ago

思路：

双指针+hash 待优化

代码

var findSubstring = function(s, words) {
    let res = [];
    let left = 0;
    let right = 0;
    let strLen = s.length;
    let wordLen = words && words[0].length || 0;
    let hash = {};
    const reset = (words) => {
        hash = {};
        words.forEach(word => {
            hash[word] =  hash[word] !== undefined ?  hash[word] + 1 : 1;
        })
    }
    reset(words, hash);
    while(right < strLen) {
        let curWord = s.slice(right, right + wordLen);
        if (hash[curWord] !== undefined) {
            hash[curWord] = hash[curWord] - 1;
            if (hash[curWord] === 0) {
                delete hash[curWord];
            }
            // 满足条件
            if (Object.keys(hash).length === 0) {
                res.push(left);
                left += 1;
                right = left;
                reset(words, hash);
            }
            else {
                right +=wordLen;
            }
        }
        else {
            left += 1;
            right = left;
            reset(words, hash);
        }
    }
    return res;
};

复杂度分析

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

SunL1GHT commented 2 years ago

思路

利用哈希表来对比words出现单词的个数和字符串中子字符串出现的个数，若相同则记录当前起始位置。

代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int n = s.length();
        int m = words.length;
        int w = words[0].length();

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

        for (String  word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i + m * w <= n; i++) {
            Map<String, Integer> cur = new HashMap<>();
            String sub = s.substring(i, i + m * w);
            for (int j = 0; j < sub.length(); j+=w) {
                String item = sub.substring(j, j + w);
                cur.put(item, cur.getOrDefault(item, 0) + 1);
            }
            if (cur.equals(map)) {
                ans.add(i);
            }
        }
        return ans;
    }
}

复杂度

时间复杂度：O(N words.length s.length())
空间复杂度：O(N * s.length())

wsmmxmm commented 2 years ago

//刚想说，我也太聪明了吧，然后超出时间限制卒。 //优化了一下，2501 ms 5% 哈哈哈哈这算暴力解法 class Solution {

public List<Integer> findSubstring(String s, String[] words) {
    boolean[] booArr = new boolean[words.length];
    List<Integer> res = new ArrayList<Integer>();
    int len = words[0].length();
    Map<String, Integer> map = new HashMap<>();
    for(String word:words){
        int temp = map.getOrDefault(word, 0);
        map.put(word, temp + 1);
    }

    int r = 0;
    int l = 0;

    char[] c = s.toCharArray();

    while(l + len <= c.length){
        r = l + len * words.length - 1;
        if(isRes2(l, r, c, map,len,words)){
            res.add(l);
        }
        l++;

    }
    return res;

}
boolean isRes2(int l, int r, char[] c, Map<String, Integer> map2, int len, String[] words){
    Map<String, Integer> map = new HashMap<>();
    for(int i = l; i <= r; i += len){
        StringBuffer sb = new StringBuffer();
        int j = i;
        while(j < c.length && sb.length() < len){
            sb.append(c[j]);
            j++;
        }
        //System.out.println("sb=:"+sb.toString()+";l=:"+l);

        int temp = map.getOrDefault(sb.toString(), 0);

        int temp2 = map2.getOrDefault(sb.toString(), 0);
        if(temp2 == 0){
            return false;
        }

        map.put(sb.toString(), temp + 1);
    }

    for(String s: words){
        int temp1 = map.getOrDefault(s, 0);
        int temp2 = map2.getOrDefault(s, 0);
        if(temp1 == 0 || temp1 != temp2){
            return false;
        }
    }
    return true;
}

}

saltychess 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 []
        sLen= len(s)
        word_sum = len(words)*len(words[0])
        word_counter = Counter(words)
        res = []
        for i in range(sLen-word_sum+1):
            flag = True
            temp_str,j = s[i:word_sum+i],0
            temp_dict = dict()
            while(j<len(temp_str)):
                word = temp_str[j:j+len(words[0])]
                if word not in word_counter:
                    flag = False
                    break
                if word not in temp_dict:
                    temp_dict[word] = 1
                else:
                    temp_dict[word] = temp_dict[word] + 1
                if word_counter[word] < temp_dict[word] :
                    flag = False
                    break
                j += len(words[0])
            if flag:res.append(i)
        return res

neado commented 2 years ago

代码

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

SamLu-ECNU commented 2 years ago

思路

首先初始化哈希表need，包含了words中所有需要匹配的单词以及出现次数。

接下来使用滑动窗口进行字符串的搜索。由于我们需要获取由单词拼接的字串，因此可以让左右指针的最小步长为len(words[0])；对于两个指针的起始位置，只需要分别以前len(words[0])个字符作为开头进行遍历即可。

在调整滑动窗口的部分中，先扩大右指针获取右边的单词r_word，如果单词出现在哈希表need中，则将窗口内维护的哈希表window对应单词出现次数加1，当window[r_word] == need[r_word]成立时，表示单词r_word的出现条件满足。而如果出现window[r_word] > need[r_word]的情况，则说明出现的单词次数多了，要通过增加左指针来缩减滑动窗口。获取窗口最左边的单词l_word，如果满足window[l_word] == need[l_word]成立，表示单词l_word的出现条件不满足，每次减少一个window[l_word]的次数。跳出循环时，如果条件满足的单词数等于len(need)，则将此时的左边界加入返回数组中。

当然，单词r_word如果没有出现在哈希表need中，我们可以直接跳过这个单词，在当前right下一个单词位置进行以上的搜索。

代码

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[0])
        t = len(need)
        res = []

        for i in range(m):
            window = defaultdict(int)
            valid = 0
            left = i
            right = i
            while right + m <= n:
                r_word = s[right: right + m]
                right += m
                if r_word in need:
                    window[r_word] += 1
                    if window[r_word] == need[r_word]:
                        valid += 1
                    while window[r_word] > need[r_word]:
                        l_word = s[left: left + m]
                        if window[l_word] == need[l_word]:
                            valid -= 1
                        window[l_word] -= 1
                        left += m
                    if valid == t:
                        res.append(left)
                else:
                    window = defaultdict(int)
                    valid = 0
                    left = right

        return res

复杂度

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

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

revisegoal commented 2 years ago

哈希表 + 滑动窗口

用哈希表map存储字符串并统计及其格数以便查找

两重循环，外循环遍历寻找子串的起点，每次内循环前使用哈希表tmp存储此次内循环单词情况，内循环遍历单词判断单词是否存在map中或tmp中该单词个数是否不超过map中个数，若否- - 内循环完成后，判断map表和tmp表是否相同（或者用count存储符合条件的word个数判断是否和words的单词个数相同），若是则将外循环起点下标添加到答案res中

class Solution {
public List<Integer> findSubstring(String s, String[] words) {
    int len = s.length();
    int wordsNum = words.length;
    int wordLen = words[0].length();
    Map<String, Integer> map = new HashMap<>();
    List<Integer> res = new LinkedList<>();
    for (int i = 0; i < wordsNum; i++) {
        map.put(words[i], map.getOrDefault(words[i], 0) + 1);
    }
    for (int i = 0; i < len - wordLen * wordsNum + 1; i++) {
        int left = i;
        Map<String, Integer> tmp = new HashMap<>();
        int count = 0;
        while (left + wordLen <= len) {
            String word = s.substring(left, left + wordLen);
            if (!map.containsKey(word)) {
                break;
            }
            tmp.put(word, tmp.getOrDefault(word, 0) + 1);
            if (tmp.get(word) > map.get(word)) {
                break;
            }
            count++;
            left += wordLen;
        }
        if (count == wordsNum) {
            res.add(i);
        }
    }
    return res;
}
}

O(n wordNum wordLen)
O(wordNum)

Kaneyang commented 2 years ago

思路

Hashtable+ Sliding Window。匹配的条件：单词数量和内容都一致

1. 计算words长度为m,words里每个单词的长度n，s的长度为ls。

2. 用哈希表统计words中每个单词出现的次数。

2. 遍历s中每个字母，取总长度为m*n的字符串，划分为m个words。遍历words，存储所有的单词，如果和words相同则储存当前字母所在的位置。循环至ls-mn的位置。

代码

from typing import List
from collections import Counter

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        m, n, ls = len(words), len(words[0]), len(s)
        counter = Counter(words)
        ans = []
        for i in range(ls):
            temp = []
            if i+m*n>ls:
                return ans
            for j in range(i,i+m*n,n):
                temp.append(s[j:j+n])
            if Counter(temp)==counter:
                ans.append(i)

复杂度分析

时间复杂度: O(ls*m)

空间复杂度: O(m)

acoada commented 2 years ago

思路

hashtable + sliding window

代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if len(words) == 0 or len(words[0]) == 0:
            return []

        word_freq = {}

        for word in words:
            if word not in word_freq:
                word_freq[word] = 0
            word_freq[word] += 1

        res = []
        words_count = len(words)
        word_length = len(words[0])

        for i in range((len(s) - words_count * word_length) + 1):
            seen = {}
            for j in range(0, words_count):
                next_word_idx = i + j * word_length
                word = s[next_word_idx: next_word_idx + word_length]
                if word not in word_freq:
                    break

                if word not in seen:
                    seen[word] = 0
                seen[word] += 1

                if seen[word] > word_freq.get(word, 0):
                    break

                if j + 1 == words_count:
                    res.append(i)
            return res

复杂度

Time: O(M*N)
Space: O(N)

ZOULUFENG commented 2 years ago

day23

使用语言：python

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        t_words = "".join(words)
        a_list = []
        len_words = len(words)
        len_words_let = len(words[0])
        s_len = len(s)
        words_dict = {}
        win_dict = {}
        if len_words == 0:
            return None

        # 获取words的字母频数
        for char in t_words:
            words_dict[char] = words_dict.get(char, 0) + 1

        left, right = 0, len(t_words)
        while right <= s_len:
            win_dict = {}
            temp_list = s[left:right]

            for index, char in enumerate(temp_list):
                win_dict[char] = win_dict.get(char, 0) + 1
                if char not in words_dict:
                    left += (index+1)
                    right += (index+1)
                    break
                elif win_dict[char] > words_dict[char]:
                    left += 1
                    right += 1
                    break
            else:
                for char in win_dict.keys():
                    if win_dict[char] < words_dict[char]:
                        left += 1
                        right += 1
                        break
                else:
                    b_list = []
                    for i in range(len_words):
                        b_list.append(temp_list[len_words_let*i:len_words_let*(i+1)])
                    for i in words:
                        if i not in b_list:
                            left += 1
                            right += 1
                            break
                        else:
                            b_list.remove(i)

                    else:

                        a_list.append(left)
                        left += 1
                        right += 1
        return a_list

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

Ye2222 commented 2 years ago

思路

滑动窗口，但是不会写，看了别人的代码，后面补个c++版本的

Code

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int n = s.length(), m = words.length, w = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (String str : words) map.put(str, map.getOrDefault(str, 0) + 1);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < w; i++) {
            Map<String, Integer> temp = new HashMap<>();
            for (int j = i; j + w <= n; j += w) {   
                String cur = s.substring(j, j + w);
                temp.put(cur, temp.getOrDefault(cur, 0) + 1);
                if (j >= i + (m * w)) {
                    int idx = j - m * w;
                    String prev = s.substring(idx, idx + w);
                    if (temp.get(prev) == 1) temp.remove(prev);
                    else temp.put(prev, temp.get(prev) - 1);
                    if (!temp.getOrDefault(prev, 0).equals(map.getOrDefault(prev, 0))) continue;
                }
                if (!temp.getOrDefault(cur, 0).equals(map.getOrDefault(cur, 0))) continue;
                if (temp.equals(map)) ans.add(j - (m - 1) * w);
            }
        }
        return ans;
    }
}

duke-github commented 2 years ago

思路

 滑动窗口

复杂度

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

代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int m = words.length, n = words[0].length(), ls = s.length();
        for (int i = 0; i < n; i++) {
            if (i + m * n > ls) {
                break;
            }
            Map<String, Integer> differ = new HashMap<String, Integer>();
            for (int j = 0; j < m; j++) {
                String word = s.substring(i + j * n, i + (j + 1) * n);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
            }
            for (String word : words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    String word = s.substring(start + (m - 1) * n, start + m * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                    word = s.substring(start - n, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }
                if (differ.isEmpty()) {
                    res.add(start);
                }
            }
        }
        return res;
    }
}

Yueza commented 2 years ago

思路

滑动窗口

代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        from collections import Counter
        ret = []
        word_len = len(words[0])
        for left in range(0, len(s)):
            word_cnt = Counter(words)
            right = left
            while word_cnt and right < len(s):
                temp_s = s[right: right + word_len]
                if temp_s not in word_cnt:
                    break
                word_cnt[temp_s] -= 1
                if word_cnt[temp_s] == 0:
                    del word_cnt[temp_s]
                right += word_len
            if not word_cnt:
                ret.append(left)
        return ret

复杂度

时间复杂度：O(s_len * word_len)
空间复杂度：O(word_num * word_len)

yingchehu commented 2 years ago

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        window_length = len("".join(words))

        # 將題目給的 words 先化成 counters，之後用來對答案
        words_dict = collections.defaultdict(int)
        for word in words:
            words_dict[word] += 1

        # 單字的長度
        word_length = len(words[0])

        # words 裡給的單字有多長，就開多少個 counter 來紀錄
        seen_dicts = [collections.defaultdict(int) for _ in range(word_length)]

        ans = []
        for r in range(len(s) - word_length + 1):
            window_head = r + word_length - window_length

            # 當前對應的 counter
            cur_counter = seen_dicts[r%word_length]

            # 將 r 指到的單字納入對應的 counter 裡
            r_word = s[r:r+word_length]
            cur_counter[r_word] += 1

            # 一旦當前 counter 存的單字數超過題目給的單字數，就要踢除最早納入的單字
            if sum(cur_counter.values()) > len(words):
                word_to_remove = s[window_head-word_length:window_head]
                cur_counter[word_to_remove] -= 1
                if cur_counter[word_to_remove] == 0:
                    del cur_counter[word_to_remove]

            # 比對當下對應的 counter 跟答案是不是一致
            if cur_counter == words_dict:
                window_head = r + word_length - window_length
                ans.append(window_head)

        return ans

複雜度

Time: O(len(s))，遍歷 s 一次
Space: O(word_length * len(words))，seen_dicts 的大小

DuanYaQi commented 2 years ago

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

思路

因为子串长度是固定的，并且个数是确定的，那么就可以用哈希表匹配

vector<int> findSubstring(string s, vector<string>& words) {
    unordered_map<string, int> ump; // 统计子串的字符个数
    for (auto &s : words) {
        ++ump[s];
    }

    int n = s.size(), cnt = words.size(), length = words[0].size();
    int childStrLen = cnt * length;
    vector<int> res;
    for (int i = 0; i < n - childStrLen + 1; ++i) {     // 遍历起始匹配位置
        string str = s.substr(i, childStrLen);          // 取出等长的字符串
        unordered_map<string, int> umpT;                // 看映射与之前的ump是否相同
        bool flag = true;
        for (int j = 0, prePos = 0; j < cnt; ++j, prePos += length) {   // 循环取出来
            string strT = str.substr(prePos, length);
            umpT[strT]++;
            if (ump.count(strT) == 0 || umpT[strT] > ump[strT]) {
                flag = false;
                break;
            }
        }
        if (flag) res.push_back(i);
    }

    return res;
}

时间复杂度: O(ls×n)，其中 ls 是输入 s 的长度，n 是 words 中每个单词的长度。需要做 n 次滑动窗口，每次需要遍历一次 s。

空间复杂度: O(m×n)，其中 m 是 words 的单词数，n 是 words 中每个单词的长度。每次滑动窗口时，需要用一个哈希表保存单词频次。

模板

无模板

MaylingLin commented 2 years ago

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        ans = []
        count = collections.Counter(words)
        n = len(words)
        m = len(words[0])
        for i in range(0, len(s) - m*n + 1):
            d = count.copy()
            for j in range(i, i + m * n, m):
                tmp = s[j: j + m]     
                flag = True              
                if tmp not in words or d[tmp] == 0:
                    flag = False
                    break
                else:
                    d[tmp] -= 1
            if flag:
                ans.append(i)
        return ans

Irenia111 commented 2 years ago

public static List<Integer> findSubstring(String s, String... words) {
`List<Integer> list = new ArrayList<>();
    if (s.length() == 0 || words.length == 0)
        return list;
    int len = words[0].length();
    if (s.length() < words.length * len)
        return list;
    int idx = -1;
    char[] sCharS = s.toCharArray();
    Set<Integer> allSet = new HashSet<Integer>();// 存储在字符串S所有匹配的下标 去重 排序
    Map<String, Integer> wordMap = new HashMap<>();// 存储 word中各个单词的个数
    Map<Integer, String> idxMap = new HashMap<>();// 存储字符串s各下标对应的单词
    for (String word : words) {
        if (wordMap.containsKey(word)) {
            wordMap.put(word, wordMap.get(word) + 1);
            continue;
        }
        char[] tem = word.toCharArray();
        while ((idx = indexOf(sCharS, sCharS.length, tem, len, idx + 1)) > -1) {
            idxMap.put(idx, word);
            allSet.add(idx);
        }
        wordMap.put(word, 1);
    }

    String word;
    int slideLen = len * words.length;// 滑块长度
    int n;// 临时变量
    Map<String, Integer> temWordMap = new HashMap<>();
    for (int k = 0; k < len; k++) {
        int flagNum = 0;// 表示滑块中有效的单词个数
        for (int i = -1, j = k; j <= sCharS.length - len; j += len) {
            if (allSet.contains(j)) {
                if (i == -1) {// 初始化滑块
                    i = j;
                    flagNum = 0;
                    temWordMap.clear();
                    temWordMap.putAll(wordMap);
                }
                // 滑块长度增加 在尾部添加
                word = idxMap.get(j);
                n = temWordMap.get(word) - 1;
                temWordMap.put(word, n);
                if (n >= 0)
                    flagNum++;
                if (j - i >= slideLen) {// 滑块长度减小 吐出头部数据
                    word = idxMap.get(i);
                    n = temWordMap.get(word) + 1;
                    temWordMap.put(word, n);
                    if (n > 0)
                        flagNum--;
                    i += len;
                }
                if (flagNum == words.length)
                    list.add(i);
            } else {
                i = -1;// j所在的位置不是给定的单词 ，销毁滑块
            }
        }
    }
    return list;

}

cyang258 commented 2 years ago

思路

we first use hashmap to store the number of word in words list, then we use sliding window technique to solve the problem

public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        HashMap<String, Integer> map = new HashMap<>();
        int wordLen = words[0].length();
        int strLen = s.length();
        int numOfWords = words.length;
        for(String word : words){
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for(int slowPtr = 0; slowPtr < wordLen; slowPtr++){
            int count = 0;
            HashMap<String, Integer> copyMap = new HashMap<>(map);
            for(int fastPtr = slowPtr; fastPtr <= strLen - wordLen; fastPtr += wordLen){
                String cur = s.substring(fastPtr, fastPtr + wordLen);
                copyMap.put(cur, copyMap.getOrDefault(cur, 0) - 1);
                if(copyMap.get(cur) >= 0){
                    count++;
                }
                int pop_start = fastPtr - numOfWords * wordLen;
                if(pop_start >= 0){
                    String pop_word = s.substring(pop_start, pop_start + wordLen);
                    copyMap.put(pop_word, copyMap.getOrDefault(pop_word, 0) + 1);
                    if(copyMap.get(pop_word) > 0)
                        count--;
                }
                if(count == numOfWords){
                    res.add(pop_start + wordLen);
                }
            }
        }
        return res;
    }

Time Complexity: O(N*M) where n is (length of string / length of words list) and m is length of word

Space Compelxity: we use two hashMap to store, so it is O(N) where n is length of words list

q815101630 commented 2 years ago

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        cnt = collections.defaultdict(int)
        total = 0
        for w in words:
            cnt[w] += 1
            total += 1
        if not s or not total:
            return []
        n = len(words[0])    
        size = n * total
        if len(s) < size:
            return []

        left, right = 0, size - 1
        ans = []
        while right <= len(s):

            curL = left
            curTotal = total
            curCnt = cnt.copy()

            invalid = False
            while curL <= right:
                if s[curL: curL+n] in curCnt and curCnt[s[curL:curL+n]] > 0:
                    curTotal -= 1
                    curCnt[s[curL:curL+n]] -= 1

                    curL += n
                else:
                    invalid = True
                    break

            if invalid:
                left += 1
                right += 1
                continue
            if curTotal == 0:
                ans.append(left)

            left += 1
            right += 1
        return ans

suukii commented 2 years ago

Time: $O((n-k)*k)$. n is the length of s and k is the length of a word.

Space: $O(m)$. m is the number of words.

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

    vector<int> res;
    int word_len = words[0].size();
    int str_len = words.size() * word_len;
    int p = 0;

    while (p + str_len <= s.size()) {
        unordered_map<string, int> freq_copy = freq;
        int q = p;

        while (q < p + str_len) {
            string w = s.substr(q, word_len);

            if (freq_copy.find(w) == freq.end()
                || freq_copy[w] == 0) {
                p++;
                break;
            }

            freq_copy[w]--;
            q += word_len;
        }

        if (q - p == str_len) {
            res.emplace_back(p);
            p++;
        }
    }

    return res;
}
};

mo-xiaoxiu commented 2 years ago

思路

遍历字符串s，遍历长度为words中一个单词的长度，注意遍历位置之后加上words中的所有单词长度之和不超出s的长度
使用哈希表作为滑动窗口，初始化滑动窗口，将s字符串以words中的单词数量放入，并对比哈希表（滑动窗口）中有没有可以抵消的
之后遍历整个字符串，以words中的单词长度为遍历单位，实现滑动窗口的右移，超出滑动窗口长度左侧减去相应的单词
记录遍历过程中滑动窗口是否为空（哈希表为空），则表示此时滑动窗口中的单词与words中的单词完全抵消，此时记录滑动窗口最左端索引加入结果集，表示找到一个答案

具体实现

class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        vector<int> res;
        int wsize = words.size(), singleWord = words[0].size(), sLen = s.size();
        for (int i = 0; i < singleWord && i + wsize * singleWord <= sLen/*保证遍历过程不会超过s的长度*/; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < wsize; ++j) { //初始化滑动窗口
                ++differ[s.substr(i + j * singleWord, singleWord)];
            }
            for (string &word: words) { //消除滑动窗口中的与word相同的单词
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }

            //当前遍历字符开始，以word中单词长度为索引长度单位
            for (int start = i; start <= sLen - wsize * singleWord; start += singleWord) {
                if (start != i) {
                    // 窗口向右移动
                    string word = s.substr(start + (wsize - 1) * singleWord, singleWord);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    // 滑动窗口超出
                    word = s.substr(start - singleWord, singleWord);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                } //滑动窗口不断移动
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};