題目:

字符串的排列

解法:

只要在一個(gè)s1長(zhǎng)度的固定大小的窗口內(nèi), 如果有其中的字符數(shù)量相等, 即認(rèn)為第一個(gè)字符串s1的排列之一是第二個(gè)字符串s2的子串

public boolean checkInclusion(String s1, String s2) {
    if (s1 == null || s2 == null) {
        return false;
    }
    if (s1 == "") {
        return true;
    }
    if (s1.length() > s2.length()) {
        return false;
    }
    int[] s1CharCount = new int[26];
    int[] slidingWindow = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        // 對(duì)應(yīng)字符相加
        s1CharCount[s1.charAt(i) - 'a']++;
    }

    int s1Len = s1.length();
    // 窗口左邊界, 包含
    int lo = 0;
    // 窗口右邊界, 包含
    int hi = s1Len - 1;

    // 初始化窗口的字符個(gè)數(shù), 暫時(shí)不包含hi
    for (int i = lo; i < hi; i++) {
        slidingWindow[s2.charAt(i) - 'a']++;
    }

    while (hi < s2.length()) {
        slidingWindow[s2.charAt(hi) - 'a']++;
        // 對(duì)比兩個(gè)數(shù)組是否相等
        if (Arrays.equals(s1CharCount, slidingWindow)) {
            return true;
        } else {
            slidingWindow[s2.charAt(lo++) - 'a']--;
        }
        hi++;
    }
    return false;
}