567. 字符串的排列
問題
給定兩個字符串 和
读慎，寫一個函數(shù)來判斷
是否包含
的排列崇众。
換句話說岭参，第一個字符串的排列之一是第二個字符串的子串到千。
示例1:
輸入:
輸出:
解釋:包含
的排列之一
.
示例2:
輸入:
輸出:
注意：
- 輸入的字符串只包含小寫字母
- 兩個字符串的長度都在 [1, 10,000] 之間
解法
題目乍一看似乎沒什么好辦法签夭，暴力遍歷總是行得通齐邦。但是時間復雜度嘛，嘿嘿第租。
接下來深挖一下題目措拇，既然是判斷是否包含
，那么我們總是可以排除一些明顯不滿足條件的地方：
-
-
接下來慎宾，我們假設中有
的排列
丐吓，那么這個排列
的長度肯定是
的長度
，實際上就是判斷這兩個字符串不管字母順序是否相同趟据，
判斷兩個字符串是否相同可以用一個長度為26的數(shù)組券犁，遍歷第一個，將字母出現(xiàn)的次數(shù)記下來汹碱，然后遍歷另一個字符串將數(shù)組中字母出現(xiàn)的次數(shù)減小一粘衬，當次數(shù)減小到-1時，代表不相同，直接返回false稚新。當遍歷完仍然沒有返回時勘伺，那么兩個字符串肯定是相同的。
我們可以設置兩個指針枷莉，一個起始指針娇昙，一個結束指針
，并且有
笤妙。此時冒掌，從
指針處往回判斷。至于為什么從
處往回走而不是從
處往前走是因為蹲盘，我們注意到這樣一種情況股毫，當
處的字符在數(shù)組中出現(xiàn)次數(shù)已經減到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;
}
}
