字符串的排列

发表于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

LeetCode每日一题，567. Permutation In String

先看题目描述

ywUgaj.png

大意就是给定两个字符串 s1 和 s2，让我们判断 s2 是否包含 s1 的排列

算法和思路

滑动窗口

设 s1 长度为 m，于是我们可以构造一个长度为 m 的滑动窗口，在 s2 中滑动，每次判断滑动窗口内的子字符串是否是 s1 的排列，若是的话则直接返回 true；若不是的话，则移动滑动窗口，移动时借鉴了 Sunday 算法的思路，每次移动时从滑动窗口的尾部从后往前寻找第一个不符合要求的位置，然后将滑动窗口移到该位置的后一位。若最后也没找到一个子字符串是 s1 的排列，则返回 false

对该方法的优化：

这个是看题解时看到的，之前我是用 cnt 维护了字符的个数，而优化的思路是用 cnt 维护两个字符串的字符差异

我们可以用一个变量 diff 来记录 cnt1 与 cnt2 的不同值的个数，这样判断 cnt1 和 cnt2 是否相等就转换成了判断 diff 是否为 0

每次窗口滑动，记一进一出两个字符为 x 和 y

若 x = y 则对 cnt2 无影响，可以直接跳过

若 x 和 y 不相等，对于字符 x，在修改 cnt2 之前若有 cnt2[x] = cnt1[x]，则将 diff 加一；在修改 cnt2 之后若有 cnt2[x] = cnt1[x]，则将 diff 减一，字符 y 同理

此外，为简化上述逻辑，我们可以只用一个数组 cnt，其中 cnt[x] = cnt2[x] - cnt1[x]，将 cnt1[x] 与 cnt2[x] 的比较替换成 cnt[x] 与 0 的比较

双指针

这也是看题解才知道 的方法

初始时，仅统计 s1 中的字符，则 cnt 的值均不为正，且元素值之和为 −n

然后用两个指针 left 和 right 表示考察的区间 [left, right]。right 每向右移动一次，就统计一次进入区间的字符 x。为保证 cnt 的值不为正，若此时 cnt[x] > 0，则向右移动左指针，减少离开区间的字符的 cnt 值直到 cnt[x] ≤ 0

注意到 [left, right] 的长度每增加 1，cnt 的元素值之和就增加 1。当 [left, right] 的长度恰好为 n 时，就意味着 cnt 的元素值之和为 0。由于 cnt 的值不为正，元素值之和为 0 就意味着所有元素均为 0，这样我们就找到了一个目标子串

算法源码

滑动窗口

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
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        if (m > n) {
            return false;
        }
        int[] cnt = new int[26];
        char[] ss1 = s1.toCharArray();
        char[] ss2 = s2.toCharArray();
        for (char c: ss1) {
            cnt[c - 'a']++;
        }
        int index = 0;
        while (index <= n - m) {
            if (isPermutation(ss2, index, m, cnt)) {
                return true;
            }
            int[] freq = Arrays.copyOfRange(cnt, 0, 26);
            int pre = index;
            index = index + m - 1;
            for (; index >= pre; index--) {
                freq[ss2[index] - 'a']--;
                if ((freq[ss2[index] - 'a']) < 0) {
                    break;
                }
            }
            index++;
        }
        return false;
    }

    private boolean isPermutation(char[] ss, int index, int len, int[] cnt) {
        int[] freq = Arrays.copyOfRange(cnt, 0, 26);
        for (int i = 0; i < len; i++) {
            int num = ss[index + i] - 'a';
            freq[num]--;
            if (freq[num] < 0) {
                return false;
            }
        }
        return true;
    }
}

优化 cnt 数组

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
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2.charAt(right) - 'a';
            ++cnt[x];
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                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
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2.charAt(right) - 'a';
            ++cnt[x];
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
}