[刷题防痴呆] 0567 - 字符串的排列 (Permutati

题目地址

https://leetcode.com/problems/permutation-in-string/

题目描述

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

思路

• 滑动窗口, 双指针.

关键点

代码

• 语言支持：Java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        char[] sc1 = s1.toCharArray();
        char[] sc2 = s2.toCharArray();
        int len1 = sc1.length;
        int len2 = sc2.length;
        int[] count = new int[256];

        for (int i = 0; i < len1; i++) {
            count[sc1[i]]++;
        }
        for (int left = 0, right = 0; right < len2; right++) {
            count[sc2[right]]--;
            while (count[sc2[right]] < 0) {
                count[sc2[left]]++;
                left++;
            }
            if (right - left + 1 == len1) {
                return true;
            }
        }

        return false;
    }
}

// 两个数组分别计数
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        char[] sc1 = s1.toCharArray();
        char[] sc2 = s2.toCharArray();
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for (int i = 0; i < sc1.length; i++) {
            count1[sc1[i] - 'a']++;
        }
        for (int left = 0, right = 0; right < sc2.length; right++) {
            count2[sc2[right] - 'a']++;
            while (count2[sc2[right] - 'a'] > count1[sc2[right] - 'a']) {
                count2[sc2[left] - 'a']--;
                left++;
            }
            if (right - left + 1 == sc1.length) {
                return true;
            }
        }

        return false;
    }
}