leetcode-438

438. Find All Anagrams in a String

LeetCode

I solved this problem using C++.
My idea: use unordered_map to store the count of characters in p, use lt and rt to represent the left and right pointers of the sliding window, and check if the current window is valid.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution
{
public:
    bool checkValidWindow(unordered_map<char, int> &p_count)
    {
        for (auto it : p_count)
        {
            if (it.second != 0)
            {
                return false;
            }
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p)
    {
        unordered_map<char, int> p_count, s_count;
        if (s.size() < p.size()) return {};
        for (char c : p)
        {
            p_count[c]++;
        }
        s_count = p_count;
        vector<int> result;
        int lt = 0, rt = 0, s_len = s.size();
        while (rt < s_len)
        {
            char ch = s[rt];
            if (p.find(ch) != string::npos)
            {
                // found in p_count
                if (s_count[ch] > 0)
                {
                    s_count[ch]--;
                    if (checkValidWindow(s_count))
                    {
                        result.push_back(lt);
                        s_count[s[lt]]++;
                        lt++;
                    }

                }
                else if (s_count[ch] == 0)
                {
                    // already in the window
                    int i = lt;
                    for (; i < rt; i++)
                    {
                        s_count[s[i]]++;
                        if (s[i] == ch)
                        {
                            lt = i + 1;
                            break;
                        }
                    }
                    s_count[ch]--;
                }
            }
            else
            {
                // not found in p_count
                s_count = p_count;
                lt = rt + 1;
            }
            rt++;
        }
        return result;
    }
};

e.g.
input: s = “ababababab” p = “aab”
output: [0, 2, 4, 6, 8]

  1. for ab in index 01, key in s_count value is 0
  2. now a in index 2, value of s_count of a is 0, now window is valid because value for key in p is all 0, result add lt
  3. move lt to right a step, move rt to right a step, check if the window is valid…
  4. find b in index 3, and bab in index 123 is not qualified with p, so find the current ch b in previous str from left, and remove it and its left part str, now count from new lt to rt, and check if the window is valid.

e.g.
input: s = “cbaebabacd”, p = “abc”
output: [0, 6]

  1. for cba in index 012, key in s_count value is 0 and it is valid
  2. not e in index 3, so reset s_count to p_count, and move lt to rt + 1
  3. bab in index 456, and b in index 6 is duplicated, so find the current ch b in previous str from left, and remove it and its left part str, now count from new lt to rt, and check if the window is valid.
  4. now lt is 5 because b in index 4 is removed, and rt is 7, now a and b is value 0, need to find c…

use certain size sliding window

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
class Solution
{
public:

    vector<int> findAnagrams(string s, string p)
    {
        int s_len = s.length(), p_len = p.length();
        if (s_len < p_len) return {};
        vector<int> result;
        vector<int> s_count(26), p_count(26);
        for (int i = 0; i < p_len; i++)
        {
            p_count[p[i] - 'a']++;
            s_count[s[i] - 'a']++;
        }

        if (s_count == p_count)
        {
            result.push_back(0);
        }

        for (int i = 0; i < s_len - p_len; i++)
        {
            --s_count[s[i] - 'a'];
            ++s_count[s[i + p_len] - 'a'];
            if (s_count == p_count)
            {
                result.push_back(i + 1);
            }
        }

        return result;
    }
};

maintain a sliding window of size p_len, and check if the current window is valid by comparing the count of characters in s and p. If they are equal, add the starting index of the window to the result.

conclusion

I think it is the same as the previous problem by using sliding window…😏😋