【算法挨揍日记】day08——30. 串联所有单词的子串、76. 最小覆盖子串

墨蓝 2024-03-02 10:23 21阅读 0赞

![6435b0e4e4bc42e480405c2d4cd984ff.png][]

## 30. 串联所有单词的子串 ##

[30. 串联所有单词的子串][30.]

### 题目描述： ###

给定一个字符串 `s`和一个字符串数组 `words`**。** `words` 中所有字符串 **长度相同**。

`s`中的 **串联子串** 是指一个包含 `words` 中所有字符串以任意顺序排列连接起来的子串。

*  例如，如果 `words = ["ab","cd","ef"]`， 那么 `"abcdef"`， `"abefcd"`，`"cdabef"`， `"cdefab"`，`"efabcd"`， 和 `"efcdab"` 都是串联子串。 `"acdbef"` 不是串联子串，因为他不是任何 `words` 排列的连接。

返回所有串联子串在 `s`中的开始索引。你可以以 **任意顺序** 返回答案。

### ![532a8d8b928f4139beb41334c02b259e.png][] ###

### 解题思路： ###

> 首先题目表示word的单词每个长度都一样，我们设为len
> 
> 我们通过暴力解法来分析一下，当我们每次移动下标都下标可以+len
> 
> ![c471fdcb2b75441093860fc310d938fe.png][]
> 
> 当然我们可能会从第一个字符开始判断也可以从第二个字符开始判断，因此第一个示例就有以下几种情况：
> 
> ![56b4fdc31da04763b5048204abe1f0e4.png][] 也就是有len种情况
> 
> 我们可以利用滑动窗口+哈希表来解决这个问题
> 
> 我们还需要使用一个代表有效个数的变量count
> 
> 1.进窗口——hash2【in】++，当hash2<=hash1, count++(in为要进窗口的下标的字符串)
> 
> 2. 判断——当m\*len>right-left+1(m为s.size（））
> 
> 3.更新结果——ret.push一下
> 
> 4.出窗口——当hash2<=hash1，count--，hash2【out】--，left+=len（out为要出窗口的下标的字符串）
> 
> 这里我写了hash1.count（in）和hash1.count（out）是为了提升速度

### 解题代码： ###

class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) {
            vector<int>ret;
            unordered_map<string,int> hash1;
            for(auto& i:words) hash1[i]++;
            int len=words[0].size();int m=words.size();
            for(int i=0;i<len;i++)
            {
               unordered_map<string,int> hash2;
               int count=0;
               for(int left=i,right=i;right<s.size();right+=len)
               {
                string in=s.substr(right,len);
                hash2[in]++;
                if(hash1.count(in)&&hash2[in]<=hash1[in])count++;
                if(m*len<right-left+1)
                {
                    string out=s.substr(left,len);
                    if(hash1.count(out)&&hash2[out]<=hash1[out])count--;
                    hash2[out]--;
                    left+=len;
                }
                if(m==count)ret.push_back(left);
               }
            }
            return ret;
        }
    };

--------------------

## 76. 最小覆盖子串 ##

[76. 最小覆盖子串][76.]

### 题目描述： ###

给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` 。

**注意：**

*  对于 `t` 中重复字符，我们寻找的子字符串中该字符数量必须不少于 `t` 中该字符数量。
 *  如果 `s` 中存在这样的子串，我们保证它是唯一的答案。

![0cd5043c75bf4e8098257e5b57295a9e.png][]

### 解题思路： ###

> 本题还是滑动窗口+哈希
> 
> 利用count和kind来解决这个问题（count为有效字符的个数，kind为种类个数）
> 
> 1.进窗口——hash2\[in\]++，当in这个字符的个数达到要求，count++
> 
> 2.判断——count==kind
> 
> 3.更新结果——当length > right - left + 1，记录一下length和begin
> 
> 4.出窗口

### 解题代码： ###

class Solution {
    public:
        string minWindow(string s, string t) {
            unordered_map<char, int> hash1;
            int kind = 0;//有效字符的种数
            for (auto& i : t) if (hash1[i]++ == 0)kind++;
            int count = 0;//有效字符个数（包括数量）的种类
            unordered_map<char, int>hash2;
            int length = INT_MAX;
            int begin=-1;
            for (int left = 0, right = 0; right < s.size(); right++)
            {
                char in = s[right];
                hash2[in]++;
                if (hash2[in] == hash1[in])count++;
                while(count == kind)
                {
                    if (length > right - left + 1)
                    {
                        length = right - left + 1;
                        begin=left;
                    }
                    char out = s[left];
                     if (hash2[out]--==hash1[out])count--;
                        out = s[++left];
                }
            }
            if(begin==-1)return "";
            string str=s.substr(begin,length);
            return str;
        }
    };

![713de93a61f74b2b813666c3e6c32683.gif][]

[6435b0e4e4bc42e480405c2d4cd984ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/dfe368d42d214c3eb5c4d379723a743f.png
[30.]: https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
[532a8d8b928f4139beb41334c02b259e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/853fad061db145699785a6f69b44697c.png
[c471fdcb2b75441093860fc310d938fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/0b3b06c33f174525b83ec898783931ee.png
[56b4fdc31da04763b5048204abe1f0e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/c9e68f79613d495ab3d64115ba7e0f0f.png
[76.]: https://leetcode.cn/problems/minimum-window-substring/
[0cd5043c75bf4e8098257e5b57295a9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/61ef7bce836946b29511d781caa9d2cd.png
[713de93a61f74b2b813666c3e6c32683.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/59ee31596b364897bcaf80162f807ec4.png