Fork me on GitHub

Permutation in String

Posted on

Description

https://leetcode.com/problems/permutation-in-string/description/

TLE Solution - DFS

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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int sizeA = s1.size();
        int sizeB = s2.size();
        if (sizeA == 0) return true;
        unordered_map<char, int> counter;
        for (int i = 0; i < sizeA; ++i) {
            ++counter[s1[i]];
        }
        
        for (int i = 0; i < sizeB; ++i) {
            if (counter.find(s2[i]) != counter.end() && counter[s2[i]] > 0) {
                --counter[s2[i]];
                if (counter[s2[i]] == 0) counter.erase(s2[i]);
                if (counter.size() == 0) return true;
                if (helper(counter, s2, i + 1, sizeB)) return true;
                ++counter[s2[i]];
            }
        }
        return false;
    }
    
    bool helper(unordered_map<char, int> counter, string& s2, int index, int sizeB) {
        for (int i = index; i < sizeB; ++i) {
            if (counter.find(s2[i]) == counter.end() 
                    || counter[s2[i]] == 0) return false;
            if ((--counter[s2[i]]) == 0) counter.erase(s2[i]);
            if (counter.size() == 0) return true;
        }
        return false;
    }
};

Sliding Windows

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int sizeA = s1.size();
        int sizeB = s2.size();
        if (sizeA > sizeB) return false;
        vector<int> counter1(26), counter2(26);
        for(int i = 0; i < sizeA; ++i) {
            ++counter1[s1[i]-'a'];
            ++counter2[s2[i]-'a'];
        }
        
        if (counter1 == counter2) return true;
        
        for (int i = sizeA; i < sizeB; ++i) {
            ++counter2[s2[i]-'a'];
            --counter2[s2[i-sizeA]-'a'];
            if (counter1 == counter2) return true;
        }
        
        return false;
    }
};