【Day 23 】2024-04-30 - 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"] 输出：[]

[xil324]

var findSubstring = function (s, words) {
    const wordFreqCounts = {};
    for (const word of words) {
        if (!(word in wordFreqCounts)) {
            wordFreqCounts[word] = 1
        }else {
            wordFreqCounts[word] += 1; 
        }
    }
    const res = []; 
    const wordLen = words[0].length; 

    for(let i = 0; i < wordLen; i++) {
        let currMap = {}; 
        let left = i, right= i, validWords = 0; 
        while(right + wordLen <= s.length) {
            const curr = s.slice(right, right + wordLen);
            right += wordLen; 
            if(!(curr in wordFreqCounts)) {
                currMap = {};
                left = right;
                validWords = 0; 
                continue;
            }
            if(currMap[curr]) {
                currMap[curr] += 1;
            }else {
                currMap[curr] = 1; 
            }
            validWords+=1;
            while(currMap[curr] > wordFreqCounts[curr]) {
                const wordToDelete = s.slice(left, left + wordLen); 
                currMap[wordToDelete] -= 1;
                left += wordLen;
                validWords -=1;
            }

            if(validWords === words.length) {
                res.push(left)
            }
        }
    }
    return res;
};

[maike-hps]

def findSubstring(s, words): def helper(word_dict, start): for i in range(len(words)): word = words[i] index = (i + start) % len(words) if word_dict[word] > 0: word_dict[word] -= 1 else: return False return True

word_count = {word: 0 for word in words}
for word in words:
    word_count[word] += 1
n, k = len(s), len(words)
result = []

for i in range(n - k * len(words[0]) + 1):
    if helper(word_count.copy(), i // len(words[0])):
        result.append(i)

return result

[CathyShang]

思路

如何判断s与words所有字符串组合相等？

• words中出现的每个字符频率 与 s对应长度切片每个字符频率是否相等；

• s对应长度切片等分后每个string是否与words中的string相等。

• 构造hashmap 共4个:

  • hash_word words中出现的每个字符频率
  • hash_q words中的string出现频率
  • hash_s s对应长度切片每个字符频率
  • hash_z s对应长度切片等分后每个string出现频率

• 固定大小的滑动窗口遍历字符串s

  • 判断hash_word==hash_s，若是则进行下一步
  • 判断hash_q==hash_z，返回答案索引

Code

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int pern = words[0].size();
        int n = words.size();
        int lengths = n*pern;
        cout << pern << ":" << n << ":" << lengths << endl;
        unordered_map<char, int> hash_word;
        unordered_map<string, int> hash_q;
        // 统计出现频次 char hash_word/ string hash_q
        for(int i=0; i<n; i++){
            hash_q[words[i]]++;
            for(int j=0; j<pern; j++){
            hash_word[words[i][j]]++;
            }
        }
        // cout << hash_word['o'] << endl;
        int sn = s.size();
        if(lengths > sn) return {};
        // 统计出现频次 char 
        int r = lengths;
        int l = 0;
        vector<int> res;
        while(r < sn+1){
            // cout<<s.substr(l,lengths)<<endl;
            string temp = s.substr(l,lengths);
            unordered_map<char, int> hash_s;
            for(int i = 0; i<lengths; i++){
            hash_s[temp[i]]++;
            }
            if(hash_s == hash_word){
            // cout << "yes" << endl;
            // 选出的字符串 每一个字符串判断
            unordered_map<string, int> hash_z;\
            int k = 0;
            while(k<lengths-pern+1){
                // cout << k << endl;
                string aa = temp.substr(k, pern);
                // cout<<aa<<endl;
                hash_z[aa]++;
                k += pern;
            }

            if(hash_z == hash_q){
            res.push_back(l);
            // cout << "res:" << l << endl;
            }
            }else{
            // cout << "no" << endl;
            }
            r++;
            l++;
        }        
        return res;
    }
};

复杂度

时间复杂度: $O(n{m}{k})$ n为words元素个数，k为words元素长度, m为s长度

空间复杂度: $O(m)$

[luzhaofeng]

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])
        word_num = len(words)
        n = len(s)
        words = Counter(words)
        res = []
        for i in range(0, one_word):
            cur_cnt = 0
            left = i
            right = i
            cur_Counter = Counter()
            while right + one_word <= n:
                w = s[right:right + one_word]
                right += one_word
                cur_Counter[w] += 1
                cur_cnt += 1
                while cur_Counter[w] > words[w]:
                    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

[Martina001]

class Solution { public List findSubstring(String s, String[] words) { List res = new ArrayList<>(); HashMap<String, Integer> need = new HashMap<>(words.length); int wordSize = words[0].length(); int len = words.length * wordSize; for (String w : words) { need.put(w, need.getOrDefault(w, 0) + 1); }

        int n = s.length();
        if (n < len) return res;

        // 这道题有三个点没有考虑到，1 就是在需要循环wordSize次进行单词分割

// 2 就是need不能--，只能window++ 这样重新开始的时候need不用动，window直接clear就行（直接不用window而是用need--也可，但是理解上有点难度） // 3 就是一定right要先加加，出窗口用window和need对比判断，用while而不用if，这样valid==0的时候窗口不用再缩小了

// 为啥循环wordSize次呢，因为循环到第wordSize+1次的时候，等价于i=0的时候情况 for (int i = 0; i < wordSize; i++) { int right = i, left = i, valid = words.length; HashMap<String, Integer> window = new HashMap<>(words.length); // 如果right + wordSize已经大于n了 就说明right后的数量不足以构成word，直接结束 while (right + wordSize <= n) { String w = s.substring(right, right + wordSize); right += wordSize;

                if (need.containsKey(w)) {
                    // 入窗口
                    window.put(w, window.getOrDefault(w,0) + 1);
                    valid--;
                    // 用while循环出窗口，所以下面valid==0的时候就不用再滑出了
                    // 这个while循环不写在下面valid==0的判断里是因为需要用到w
                    while (window.getOrDefault(w, 0) > need.getOrDefault(w, 0)) {
                        String leftString = s.substring(left, left + wordSize);
                        window.put(leftString, window.get(leftString) - 1);
                        valid++;
                        left += wordSize;
                    }
                } else {
                    // 如果当前单词不在words中，直接从下一个单词的起始点开始，window和valid记得初始化
                    left = right;
                    window.clear();
                    valid = words.length;
                    continue;
                }

                if (valid == 0) {
                    // 这里不用再滑出窗口，上面已经在while判读的时候滑出过了
                    res.add(left);

                }
            }
        }
        return res;
    }
}

[GReyQT]

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int n1 = s.length(), n2 = words.size();
        int len = words[0].length(); 
        if (n1 < n2 * len)
            return res;
        unordered_map<string, int> word1;
        unordered_map<string, int> word2;
        for (int i = 0; i < words.size(); i++) {
            word1[words[i]]++;
        }
        int p = 0, q = p + n2 * len - 1, flag = 0;
        while (q < n1) {
            for (int i = p; i <= q; i += len) {
                if (word1.find(s.substr(i, len)) != word1.end()) {
                    word2[s.substr(i, len)]++;
                    if (word2[s.substr(i, len)] > word1[s.substr(i, len)]) {
                        flag = 1;
                        break;
                    }
                } else {
                    flag = 1;
                    break;
                }
            }
            if (!flag)
                res.push_back(p);
            p++;
            q = p + n2 * len - 1;
            word2.clear();
            flag = 0;
        }
        return res;
    }
};

[Dtjk]

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

[zhiyuanpeng]

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

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

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

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