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. 初始化滑動(dòng)窗口
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
            ++cnt[s2.charAt(i) - 'a'];
        }
2. 初始化滑動(dòng)窗口的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，則現(xiàn)在differ+1
cnt[x]=cnt 2[x]?cnt 1 [x]
            if (cnt[x] == 0) {
                ++diff;
            }
            ++cnt[x];
5. 修改cn2后，若cnt[x]==0，則之前不相等，現(xiàn)在相等，即differ-1
            if (cnt[x] == 0) {
                --diff;
            }
6. 左邊界之前等于0，現(xiàn)在左移，則differ+1
            if (cnt[y] == 0) {
                ++diff;
            }
7. 左移
            --cnt[y];
8. 左移后，等于0，則之前不相等，現(xiàn)在相等，即differ-1
            if (cnt[y] == 0) {
                --diff;
            }
            if (diff == 0) {
                return true;
            }
        }
        return false;
    }
}
復(fù)雜度分析

時(shí)間復(fù)雜度：O(n+m+∣Σ∣)，其中 n 是字符串 s1的長(zhǎng)度，m 是字符串 s2的長(zhǎng)度，Σ 是字符集，這道題中的字符集是小寫字母，∣Σ∣=26。

空間復(fù)雜度：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. 初始化滑動(dòng)窗口
        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一個(gè)或多個(gè)，則左邊界右滑進(jìn)行收縮
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
}
復(fù)雜度分析

時(shí)間復(fù)雜度：O(n+m+∣Σ∣)。
創(chuàng)建 cnt 需要 O(∣Σ∣) 的時(shí)間。
遍歷 s1需要 O(n) 的時(shí)間。
雙指針遍歷 s2時(shí)，由于 left 和 right 都只會(huì)向右移動(dòng)，故這一部分需要 O(m) 的時(shí)間。

空間復(fù)雜度：O(∣Σ∣)。