567. 字符串的排列

567. 字符串的排列 - 力扣（LeetCode）

image.png

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
1. 初始化滑动窗口
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
            ++cnt[s2.charAt(i) - 'a'];
        }
2. 初始化滑动窗口的differ
        int diff = 0;
        for (int c : cnt) {
            if (c != 0) {
                ++diff;
            }
        }
        if (diff == 0) {
            return true;
        }
        for (int i = n; i < m; ++i) {
3. x为右边界，y为左边界
            int x = s2.charAt(i) - 'a', y = s2.charAt(i - n) - 'a';
            if (x == y) {
                continue;
            }
4. 右边界之前等于0，则现在differ+1
cnt[x]=cnt 2[x]−cnt 1 [x]
            if (cnt[x] == 0) {
                ++diff;
            }
            ++cnt[x];
5. 修改cn2后，若cnt[x]==0，则之前不相等，现在相等，即differ-1
            if (cnt[x] == 0) {
                --diff;
            }
6. 左边界之前等于0，现在左移，则differ+1
            if (cnt[y] == 0) {
                ++diff;
            }
7. 左移
            --cnt[y];
8. 左移后，等于0，则之前不相等，现在相等，即differ-1
            if (cnt[y] == 0) {
                --diff;
            }
            if (diff == 0) {
                return true;
            }
        }
        return false;
    }
}
复杂度分析

时间复杂度：O(n+m+∣Σ∣)，其中 n 是字符串 s1的长度，m 是字符串 s2的长度，Σ 是字符集，这道题中的字符集是小写字母，∣Σ∣=26。

空间复杂度：O(∣Σ∣)。

方法2--双指针

s1: target
s2: source
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
1. 初始化滑动窗口
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
        }
2. 右边界右滑，
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2.charAt(right) - 'a';
            ++cnt[x];
3. cnt[x]>0,说明多于target一个或多个，则左边界右滑进行收缩
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
}
复杂度分析

时间复杂度：O(n+m+∣Σ∣)。
创建 cnt 需要 O(∣Σ∣) 的时间。
遍历 s1需要 O(n) 的时间。
双指针遍历 s2时，由于 left 和 right 都只会向右移动，故这一部分需要 O(m) 的时间。

空间复杂度：O(∣Σ∣)。