567. Permutation in String 

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
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        int[] targetCountMap = new int[26];
        int targetDistinctCharCount = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (targetCountMap[s1.charAt(i) - 'a']++ == 0) {
                targetDistinctCharCount++;
            }
        }

        int[] windowCountMap = new int[26];
        int distinctCharCount = 0;
        int i = 0;
        for (int j = 0; j < s2.length(); j++) {
            int offset = s2.charAt(j) - 'a';
            if (++windowCountMap[offset] == targetCountMap[offset]) {
                distinctCharCount++;
            }

            while (distinctCharCount == targetDistinctCharCount) {
                // 当不同的字符数已经匹配时，说明窗口字符串长度大于等于目标字符串长度，此时检查字符串长度是否相同
                if (j - i + 1 == s1.length()) {
                    return true;
                }

                // 尝试缩小窗口
                int leftmostOffset = s2.charAt(i++) - 'a';
                if (windowCountMap[leftmostOffset]-- == targetCountMap[leftmostOffset]) {
                    distinctCharCount--;
                }
            }
        }

        return false;
    }
}

注意此题要求窗口字符串长度与目标字符串长度相等。

References

567. Permutation in String
剑指 Offer II 014. 字符串中的变位词