[LeetCode] 567. Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Example 1:
Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:
Input: s1 = “ab”, s2 = “eidboaoo”
Output: false

Constraints:
1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.

字符串的排列。

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意是给两个字符串 s1 和 s2，s1 较短，请问 s2 中是否包含 s1 的某个排列。还是典型的 sliding window 的解法，首先创建一个 hashmap，统计 s1 中出现的字母和次数的情况，然后设置两个 pointer start 和 end，夹住 s2 开始扫描，counter 变量初始化的时候记录的是 s1 的长度，这个 counter 虽然一开始是以长度初始化，但是实际记录的是在 s1 中出现过的字母的个数，包括重复的。遍历的时候，如果 end 碰到的是 s1 中存在的字母且 counter > 0，则 counter–。当 counter == 0 的时候，说明此时这个区间内已经收集了所有 s1 需要的字母了。同时我们需要检查一下这个区间的长度是否等于 s1 的长度，如果等于，这个区间才是 s1 的 permutation。

代码模板参见 76 题，这是一道滑动窗口的经典题。这道题唯一跟 76 题不同的地方是只要在 s2 中找到 s1 的某一个排列，就直接 return true 了，不一定需要扫描完整个 s2。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len = s1.length();
		// 统计s1中字母的个数
        int[] map = new int[256];
        for (char c : s1.toCharArray()) {
            map[c]++;
        }

        int counter = s1.length();
        int start = 0;
        int end = 0;
        while (end < s2.length()) {
            char c1 = s2.charAt(end);
            if (map[c1] > 0) {
                counter--;
            }
            map[c1]--;
            end++;
            while (counter == 0) {
                if (end - start == len) {
                    return true;
                }
                char c2 = s2.charAt(start);
                map[c2]++;
                if (map[c2] > 0) {
                    counter++;
                }
                start++;
            }
        }
        return false;
    }
}