「力扣」第 567 题：字符串的排列

发布日期: 2017-06-25

链接：https://leetcode-cn.com/problems/permutation-in-string

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2：
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：

输入的字符串只包含小写字母

两个字符串的长度都在 [1, 10,000] 之间

Java 代码：

import java.util.Arrays;

public class Solution {

    public boolean checkInclusion(String s1, String s2) {
        int sLen1 = s1.length();
        int sLen2 = s2.length();

        char[] charArray1 = s1.toCharArray();
        int[] cnt1 = new int[128];
        int[] cnt2 = new int[128];

        int distance = 0;
        for (char c : charArray1) {
            if (cnt1[c] == 0) {
                distance++;
            }
            cnt1[c]++;
        }

        int left = 0;
        int right = 0;
        int count = 0;
        char[] charArray2 = s2.toCharArray();

        while (right < sLen2) {
            // 两个 continue 都可以不要
            if (cnt1[charArray2[right]] == 0) {
                right++;
                continue;
            }

            cnt2[charArray2[right]]++;
            if (cnt2[charArray2[right]] == cnt1[charArray2[right]]) {
                count++;
            }

            right++;
            while (count == distance) {
                if (right - left == sLen1){
                    return true;
                }

                if (cnt1[charArray2[left]] == 0) {
                    left++;
                    continue;
                }

                cnt2[charArray2[left]]--;
                if (cnt2[charArray2[left]] < cnt1[charArray2[left]]) {
                    count--;
                }
                left++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = "eidbaooo";
        Solution solution = new Solution();
        boolean res = solution.checkInclusion(s1, s2);
        System.out.println(res);
    }
}