567. 字符串的排列

問題

給定兩個字符串 和 ，寫一個函數(shù)來判斷 是否包含 的排列。
換句話說，第一個字符串的排列之一是第二個字符串的子串。

示例1:

輸入:
輸出:
解釋: 包含 的排列之一 .

示例2:

輸入:
輸出:

注意：

• 輸入的字符串只包含小寫字母
• 兩個字符串的長度都在 [1, 10,000] 之間

解法

題目乍一看似乎沒什么好辦法，暴力遍歷總是行得通。但是時間復雜度嘛，嘿嘿。

接下來深挖一下題目，既然是判斷是否包含，那么我們總是可以排除一些明顯不滿足條件的地方：

• 或為空
• 的長度小于

接下來，我們假設中有的排列，那么這個排列的長度肯定是的長度，實際上就是判斷這兩個字符串不管字母順序是否相同，
判斷兩個字符串是否相同可以用一個長度為26的數(shù)組，遍歷第一個，將字母出現(xiàn)的次數(shù)記下來，然后遍歷另一個字符串將數(shù)組中字母出現(xiàn)的次數(shù)減小一，當次數(shù)減小到-1時，代表不相同，直接返回false。當遍歷完仍然沒有返回時，那么兩個字符串肯定是相同的。
我們可以設置兩個指針，一個起始指針，一個結束指針，并且有。此時，從指針處往回判斷。至于為什么從處往回走而不是從處往前走是因為，我們注意到這樣一種情況，當處的字符在數(shù)組中出現(xiàn)次數(shù)已經(jīng)減到0時，處的字符必然不在排列中，此時，可以直接跳到處，可以直接過濾掉部分字符。這樣也就不用遍歷必然失敗的場景了。

代碼

java實現(xiàn)

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //  特殊情況直接跳出
        if (s1 == null || s2 == null || s2.length() < s1.length()) {
            return false;
        }
        // 初始化一個數(shù)組，將s1的字母出現(xiàn)次數(shù)保存在這個數(shù)組中去。
        int[] map = new int[26];
        int length = s1.length();
        //遍歷s1放入map
        for (int i = 0; i < length; i++) {
            map[s1.charAt(i) - 'a']++;
        }
        //遍歷s2，此時注意到這樣一個情況，如果s2包含s1，那么s2子串的長度必然等于s1，因此，可以設置兩個指針。
        int start = 0, end = length - 1;
        while (end < s2.length()) {
            // 這里是一個注意點，需要注意不能直接用map處理，否則會導致第一次false后，后面的判斷全是false
            int[] temp = map.clone();
            while (end >= start) {
                if (temp[s2.charAt(end) - 'a']-- == 0) {
                    break;
                }
                end--;
            }
            //上一層有兩種跳出方式，一種break；一種是正確判斷完了。需要區(qū)分一下。
            if (end < start) {
                //這種是正常判斷完成了。直接返回true 
                return true;
            } else {
                //此時注意到這樣一種情況，end處必然不能在s2子串中出現(xiàn)。那么start = end+1,end = start+length-1 可以跳過start與end之間的字符，因為這部分字符必然不滿足條件。
                start = end + 1;
                end = start + length - 1;
            }
        }
        return false;
    }
}