Vault 101

xjay2007's Blog

0%

LeetCode 438. 找到字符串中所有字母异位词

发表于 分类于 ，

题目描述

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

  • 字母异位词指字母相同，但排列不同的字符串。
  • 不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
6
7
8
9
输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

1
2
3
4
5
6
7
8
9
10
输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

题解

哈希表

算法

  • 哈希表 pMap 记录 p 中所有字母出现次数。
  • 从 s 左侧开始，记录 sMap 为 i 到 i + p.length() 的子串中所有字母出现次数。与 pMap 相同则记录 i 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// C++
vector<int> findAnagrams(string s, string p) {
    const int sLen = (int)s.length();
    const int pLen = (int)p.length();
    vector<int> pMap(26, 0);
    for (char ch : p) {
        ++pMap[ch - 'a'];
    }
    vector<int> ans;
    vector<int> sMap(26, 0);
    for (int i = 0; i < sLen; ++i) {
        ++sMap[s[i] - 'a'];
        if (i >= pLen) {
            --sMap[s[i-pLen] - 'a'];
        }
        if (sMap == pMap) {
            ans.push_back(i - pLen + 1);
        }
    }
    return ans;
}

复杂度

  • 时间复杂度：$O(len(s) \times len(p))$ 。
  • 空间复杂度：$O(len(s))$ 。

滑动窗口

算法

  1. 使用 map 来记录 p 中字母出现的次数。counter 表示 map 的键值数目，即不同字母的个数。
  2. 使用 l 和 r 两个指针构建一个滑动窗口，使得 s[l:r] 符合 p 的字母异位词。
  3. 判断 r ，如果 s[r] 出现在 map 中，则做 map[s[r]]--。
  4. 如果 map[s[r]] == 0 ，表示这个字母已经都出现了，将 counter--。
  5. 窗口右侧移动，r++，回到第 3 步。
  6. 如果 counter == 0，表示 s[l:r] 子字符串中，p 的所有字母都已经出现了。
  7. 如果此时 counter == 0 && r - l == p.length，表示当前 s[l:r] 即为 p 的字母异位词。
  8. 如果 s[l] 出现在 map 中，则将 map[s[l]]++，因为 s[l] 即将被移除窗口。
  9. 如果 map[s[l]] > 0，表示这个字母不存在了，将 counter++。
  10. 窗口左侧收缩，l++，回到第 3 步。

图例

1
2
l --------------- r , 假设此时 counter == 0, 说明 p 中所有字母均已出现.
     l ---------- r , 收缩左侧窗口，保证 counter == 0 的情况下，r - l == p.length

代码

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
33
34
35
36
37
38
39
40
41
42
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const [sLen, pLen] = [s.length, p.length];
    if(sLen < pLen) {
        return [];
    }
    const map = new Map();
    for(let c of p) {
        map.set(c, map.has(c) ? (map.get(c) + 1) : 1);
    }
    let counter = map.size;
    const ans = [];
    let [l, r] = [0, 0];
    while(r < sLen) {
        const cr = s[r];
        if(map.has(cr)) {
            map.set(cr, map.get(cr) - 1);
            if(map.get(cr) === 0) {
                counter--;
            }
        }
        r++;
        while(counter === 0) {
            const cl = s[l];
            if(map.has(cl)) {
                map.set(cl, map.get(cl) + 1);
                if(map.get(cl) > 0) {
                    counter++;
                }
            }
            if(r - l === pLen) {
                ans.push(l);
            }
            l++;
        }
    }
    return ans;
};
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
33
34
vector<int> findAnagrams(string s, string p) {
    vector<int> pMap(26, 0);
    for (char ch : p) {
        ++pMap[ch - 'a'];
    }
    int left = 0;
    int right = 0;
    int count = (int)p.length();
    vector<int> ans;
    while (right < s.length()) {
        //move right everytime, if the character exists in p's hash, decrease the count
        //current hash value >= 1 means the character is existing in p
        if (pMap[s[right++] - 'a']-- >= 1) {
            --count;
        }


        //when the count is down to 0, means we found the right anagram
        //then add window's left to result list
        if (count == 0) {
            ans.push_back(left);
        }
    
        //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window
        //++ to reset the hash because we kicked out the left
        //only increase the count if the character is in p
        //the count >= 0 indicate it was original in the hash, cuz it won't go below 0
        if (right - left == p.length() && pMap[s[left++] - 'a']++ >= 0) {
            ++count;
        }
    }
    return ans;
}

复杂度

  • 时间复杂度：$O(len(s))$。
  • 空间复杂度：$O(len(p))$。

参考链接

相似文章