🟡 剑指 Offer II 014. 字符串中的变位词

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

两个词若互相为变位词，那么26个字母在两个单词中出现的次数肯定都相同。

可以用滑动窗口的思路，用两个26位数组cnt1和cnt2分别记录每个字母在两个单词中的数量，移动窗口，改变cnt2的值，然后比较两个数组是否相同。

但每次移动窗口都比较两个数组，有点累赘，可以用一个常量diff表示相差的字母数量即可。

同时可以简化只要一个26位数组记录即可，数组每一位均为0时diff=0。

由此可得，在初始化的时候，S2每个字母贡献为1，S1的为-1。

class Solution {    public boolean checkInclusion(String s1, String s2) {        int l1 = s1.length(), l2 = s2.length();        if (l1 > l2) {            return false;        }
        int[] cnt = new int[26];        int diff = 0;
        for (int i=0; i<l1; i++) {            cnt[s1.charAt(i)-'a'] -= 1;            cnt[s2.charAt(i)-'a'] += 1;        }        for (int i=0; i<26; i++) {            if (cnt[i] != 0) {                diff += 1;            }        }
        if (diff == 0) {            return true;        }
        // 窗口进入一个y，出一个x        char x, y;        for (int i=l1; i<l2; i+=1) {            x = s2.charAt(i-l1);            y = s2.charAt(i);
            if (x == y) {                continue;            }
            cnt[y-'a'] += 1;            cnt[x-'a'] -= 1;
            if (cnt[y-'a'] == 0) {                diff -= 1;a            }            if (cnt[y-'a'] == 1) {                diff += 1;            }            if (cnt[x-'a'] == 0) {                diff -= 1;            }            if (cnt[x-'a'] == -1) {                diff += 1;            }
            if (diff == 0) {                return true;            }        }
        return diff == 0;    }}

题解2 对比

顺便放一个简化前的版本，方便比较思考。（虽然题解1也是抄的）

class Solution {    public boolean checkInclusion(String s1, String s2) {        int n = s1.length(), m = s2.length();        if (n > m) {            return false;        }        int[] cnt1 = new int[26];        int[] cnt2 = new int[26];        for (int i = 0; i < n; ++i) {            ++cnt1[s1.charAt(i) - 'a'];            ++cnt2[s2.charAt(i) - 'a'];        }        if (Arrays.equals(cnt1, cnt2)) {            return true;        }        for (int i = n; i < m; ++i) {            ++cnt2[s2.charAt(i) - 'a'];            --cnt2[s2.charAt(i - n) - 'a'];            if (Arrays.equals(cnt1, cnt2)) {                return true;            }        }        return false;    }}

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/MPnaiL/solution/zi-fu-chuan-zhong-de-bian-wei-ci-by-leet-wbma/