LintCode 1169: Permutation in String 字符串处理好题

1169 · Permutation in String
Algorithms
Medium

Description
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].
Example
Example 1:

Input:s1 = “ab” s2 = “eidbaooo”
Output:true
Explanation: s2 contains one permutation of s1 (“ba”).
Example 2:

Input:s1= “ab” s2 = “eidboaoo”
Output: false
Tags
Company
Microsoft
Related Problems

32
Minimum Window Substring
Medium

647
Find All Anagrams in a String
Medium

解法1：把s1里面的permutation都找出来，然后看是不是在s2里面，这个应该是O(2^m * n)，其中m和n分别为s1和s2的长度。肯定超时，不管怎么剪枝都没用。

class Solution {
public:
    /**
     * @param s1: a string
     * @param s2: a string
     * @return: if s2 contains the permutation of s1
     */
    bool checkInclusion(string &s1, string &s2) {
        vector<int> visited(s1.size(), false);
        string sol = "";
        return helper(s1, visited, sol, s2);
    }
private:
    bool helper(string &s1, vector<int> &visited, string &sol, string &s2) {
        if (sol.size() == s1.size()) {
            if (s2.find(sol) != string::npos) return true;
            return false;
        }
        for (int i = 0; i < s1.size(); i++) {
            if (visited[i]) continue;
            visited[i] = true;
            sol = sol + s1[i];
            if (helper(s1, visited, sol, s2)) return true;
            sol.pop_back();
            visited[i] = false;
        }
        return false;
    }
};
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

解法2：滑动窗口法。s2从左到右移动，每s1长度的字符就比较freq1和freq2。时间复杂度O(n)。其中n为s2的长度。但实际上还要乘以128这个常数。这个应该不是最优。

class Solution {
public:
    /**
     * @param s1: a string
     * @param s2: a string
     * @return: if s2 contains the permutation of s1
     */
    bool checkInclusion(string &s1, string &s2) {
        int len1 = s1.size();
        int len2 = s2.size();
        if (len1 > len2) return false;
        vector<int> freq1(128, 0), freq2(128, 0);
        for (int i = 0; i < len1; i++) {
            freq1[s1[i]]++;
            freq2[s2[i]]++;
        }
        if (freq1 == freq2) return true;
        for (int i = len1; i < len2; i++) {
            freq2[s2[i]]++;
            freq2[s2[i - len1]]--;
            if (freq1 == freq2) return true;
        }
        return false;
    }
};
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

解法3: 同向双指针，时间复杂度O(n), n为s2长度。

class Solution {
public:
    /**
     * @param s1: a string
     * @param s2: a string
     * @return: if s2 contains the permutation of s1
     */
    bool checkInclusion(string &s1, string &s2) {
        vector<int> freq(128, 0);
        int len1 = s1.size(), len2 = s2.size();
        int count = len1, left = 0, j = 0;
        for (auto s : s1) freq[s]++;     
        for (int i = 0; i < len2; i++) {
            j = max(i, j); //i is left, j is right
            while (count > 0 && j < len2) {
                if (freq[s2[j]] > 0) count--;
                freq[s2[j]]--;
                j++;
            }
            if (count == 0 && j - i == len1) return true; //the window is just right
            if (freq[s2[i]] == 0) count++; // s2[i] is in s1
            freq[s2[i]]++;
        }
        return false;
    }
};
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

注意:

1. 上面的双指针是参考的模板，即for(int i)循环是移动左指针，而里面嵌套的while()是移动右指针。也可以外面的循环移动右指针，里面的循环移动左指针，比如下面的链接
   https://www.cnblogs.com/grandyang/p/6815227.html
2. 如何理解for-while循环？对于每个固定的左指针i，右指针j先往后移动，直到i…j之间包含了s1所有的字符(count == 0)。然后检查i…j的长度(注意这里长度本来是j-i+1，但j在while()里面多加了1，所以是j-i)。
   a. 如果长度刚好等于s1.size()，那么s2[i…j]就刚好是s1的一个排列，return true。
   b. 否则长度肯定大于s1.size()，但也不一定不符合要求，因为s2[i…j]的左边可能有一堆连续的不在s1里面的字符。比如说s1=“ab”，s2[i…j]="cdgba"其实也是符合要求的，因为后面的"ba"就是s1的一个排列。这种情况下继续for循环，也就是向右移动左指针i，当移动到j-i=len时，说明找到了一个合适的排列，返回true。注意移动过程中有可能 freq[s2[i]]==0，这种情况说明此时s2[i]这个字符在s1和s2[i…j]里面是匹配的，也就是该字符出现的字符在s1和s2[i…j]里面相等，因为i要移走了，count应该++。
3. 对于freq[]数组而言，一开始对s1循环，里面每个字符对应的freq[s]++。接下来的for-while循环是对s2处理，右边进window，freq[s2[j]–，左边出窗口，freq[s2[i]]++。这里不需要管对应的字符是不是在s1里面。
4. 怎么理解freq[]数组呢？在for-while循环里面，我的理解如下 (下面的陈述是在for循环内部，freq[s2[i]]++之前有效):
   freq[c] > 0 : 表示s1比s2[i…j]多freq[c]个c字符
   freq[c] < 0：表示s2[i…j]比s1多freq[c]个c字符，注意这里c字符不一定在s1里面
   freq[c] == 0：表示s1比s2[i…j]的c字符相等。
5. count代表了s1里面有多少字符跟s2[i…j]不match。如果count==0，说明s1里面的字符s2[i…j]里面都有，但s2[i…j]的长度可能>s1。可能s1是s2[i…j]的一个subarray(那样还是合格的排列)，也可能只是一个subsequence(那样就不合格)。