优选算法——滑动窗口补充

六、leetcode438.找到字符串中所有字母异位词

题目分析：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

算法原理：

​ 1.快速判断两个字符串是异位词，利用哈希表快速判断字符串的构成是否相等；

​ 2.利用滑动窗口解决；滑动窗口的大小是固定的；

代码实现：

vector<int> findAnagrams(string s, string p) {
    vector<int> v;
    int hash1[26] = {0};
    int hash2[26] = {0};
    for (auto& e : p) {
        hash2[e - 'a']++;
    }
    int left = 0, right = 0, count = 0;
    int size = s.size();
    while (right < size) {
        if (++hash1[s[right] - 'a'] <= hash2[s[right] - 'a'])
            count++;
        if (right - left > p.size() - 1) {
            if (hash1[s[left] - 'a']-- <= hash2[s[left] - 'a'])
                count--;
            left++;
        }
        if (count == p.size())
            v.push_back(left);
        right++;
    }
    return v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

七、leetcode30.串联所有单词的⼦串

题目分析：

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

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

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

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

算法原理

​ 借助异位词的方法；left right的步长变成了异位词中元素的长度，滑动窗口的执行要循环执行元素长度次，哈希表存放的是字符串；

代码实现：

​ 注意hash1需要循环三次，期间是要回退的，所以需要重置；

vector<int> findSubstring(string s, vector<string>& words) {
    int len = words[0].size();
    unordered_map<string, int> hash2;
    for (auto& e : words) {
        hash2[e]++;
    }
    vector<int> v;
    for (int i = 0; i < len; i++) {
        unordered_map<string, int> hash1;
        for (int right = i, left = i, count = 0; right + len <= s.size();
             right += len) {
            string sub = s.substr(right, len);
            ++hash1[sub];
            if (hash2.count(sub) && hash1[sub] <= hash2[sub])
                count++;
            if (right - left > (words.size() - 1) * len) {
                string sub = s.substr(left, len);
                if (hash2.count(sub) && hash1[sub] <= hash2[sub])
                    count--;
                hash1[sub]--;
                left += len;
            }
            if (count == words.size()) {
                v.push_back(left);
            }
        }
    }
    return v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

八、leetcode76.最小覆盖字串

题目分析：

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

注意：

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

算法原理：

​ 滑动窗口解决；

代码实现：

string minWindow(string s, string t) {
    int hash1[128] = {0};
    int kinds = 0;
    int hash2[128] = {0};
    for (auto& e : t) {
        if (hash2[e]++ == 0)
            kinds++;
    }
    int len = INT_MAX,  begin = -1;
    for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
        // 进窗口
        hash1[s[right]]++;
        if (hash1[s[right]] == hash2[s[right]]) {
            count++;
        }
        while (count == kinds) {
            if(len>right-left+1)
            {
                len=right-left+1;
                begin=left;
            }
            if (hash1[s[left]] == hash2[s[left]])
                count--;
            hash1[s[left++]]--;
        }
    }
    if (begin == -1) {
        return "";
    } else {
        return s.substr(begin, len);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32