先給題
給定兩個字串 s1 和 s2，寫一個函式來判斷 s2 是否包含 s1 的排列，

換句話說，第一個字串的排列之一是第二個字串的子串，

示例1:

輸入: s1 = "ab" s2 = "eidbaooo"
輸出: True
解釋: s2 包含 s1 的排列之一 ("ba").
 

示例2:

輸入: s1= "ab" s2 = "eidboaoo"
輸出: False
 

注意：

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutation-in-string
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

今天第一次，沒有看題解做出來了，時間和記憶體還都可以的情況下，繼續加油！

1.暴力破解

以后就不談暴力破解了，一般這樣的題暴力破解都超時

2.自己想的

說一說自己的想法

（1）總體思想

第一眼看到這個字串匹配的問題，就想到了滑動視窗（雙指標），最近做這樣的題蠻多的，
（看了題解才知道我用的是雙指標，雙指標和滑動視窗并不是一摸一樣的，具體區別可以看https://blog.csdn.net/WizardWXY/article/details/113703470，感覺講的蠻好的）
我們先來理解一下題，題的意思是我們要判斷s2中是否存在一個與s1等長度的子陣列，元素種類與元素個數與s1完全相同，有就回傳1，沒有就回傳0.
（一開始我是按照順序也一致做的，不管正序或者逆序，但后來發現理解錯題了，）
所以，我們要想辦法來記錄一下子字串的的元素狀況，我們開辟一個長度為26的陣列來記錄個元素的數量，這個陣列來記錄s1字串元素的情況，當右指標移動時，判斷這個元素個數是否為0，不為0代表目前子字串的元素種類和個數都沒問題，如果為0，就表明這個元素要么不存在，要么前面存在這個元素的數量已經超過了s1中的，這時候我們就要左指標移動，并且要再把左邊移動出來的元素再記錄進去，
那么記下來的問題就是如何判斷查找出符合的情況以及左指標根據什么條件移動，（這也是最難的兩個點）

（2）我們先來談一談左指標如何移動，

左指標一旦移動，就代表了當前子字串的元素種類或者數目不符合要求，左指標需要移動，那么左指標移動到什么地步，子字串就符合了？
極限的情況，我們遇到了一個s1根本不存在的元素，那么此時子字串肯定不符合要求了，讓left和right移動到這個元素的后面重新開始，
而如果我們遇到的元素是前面出現的元素，只是數量達不到要求，那么左指標只要移動到與該元素相同的那個元素的后面，我們就可以不用再移動了，此時子字串肯定符合要求，
根據上面的兩種情況，我們可以得出，只要右指標指向的元素的可用值為0，我們左指標就要一直移動，直到左指標達到右指標的位置，當左指標不再移動時，再來判斷右指標指向元素是否大于0（因為右指標指向的元素不存在，那么左指標就移動到右指標的位置，所以還需要在判斷一下數值），大于0，就說明這個元素是存在于s1的，記錄影響值，=0，就說明這個元素不存在，左指標繼續移動一位，跳過這個元素，

（3）再來談一下判斷有無的條件

一開始我是這么想的，當這個記錄數值的26位陣列所有值都為0的時候，就代表著元素全部用完了，但這樣太費時了，
所以我們來找另一種判斷的方法，
假設一開始我們就沒遇到不符合的元素，那么右指標一直移動，當這個子陣列元素情況與s1相等時，此時我們就可以判斷它是符合條件的，這樣的話如果我們遇到不符合的元素，那么此時右指標減去左指標+1 一定是小于等于s1的長度的，
根據上述假設，我們就可以知道，當判斷后如果右指標減去左指標+1（即當前子陣列長度）達到了s1的長度，那么我們就可以說存在符合題意的子陣列了，

（4）理解完了就上代碼

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
    int left = 0, right = 0;
    vector<int> v(26, 0);
    for (int i = 0; i < s1.length(); i++)
        v[(int)s1[i] - 97]++;
    while (right < s2.length()) {
        if (v[(int)s2[right] - 97] > 0) 
            v[(int)s2[right] - 97]--;
        else
        {
            while (v[(int)s2[right] - 97] == 0 && left < right) {
                v[(int)s2[left] - 97]++;
                left++;
            }
            if (v[(int)s2[right] - 97] > 0) 
                v[(int)s2[right] - 97]--;
            else
                left++;
        }
        right++;
        if (right - left == s1.length()) 
            return 1;
        
    }
    return 0;
}
};

3.題解

題解有兩種，一種是滑動視窗，一種是雙指標（和我想的一摸一樣），所以在這里我們就來說滑動視窗，
其實思路差不很多，我們依然是開辟陣列來記錄元素的狀況，只不過這次我們是來記錄兩個子陣列的情況，
要想符合題意，s2的子陣列長度肯定是s1的長度，所以只要兩個陣列的元素情況相同，我們就可以回傳1，左指標跟著右指標移動，視窗的長度固定不變，

官方題解還對這個方法進行了優化，我們可以只開辟一個陣列來記錄情況，這個陣列用來記錄上述方法中用來記錄元素狀況的兩個陣列的差，判斷條件我們可以用一個diff來記錄他們的不同值，當差不為0，就讓diff++，只要diff不為0，那么就不符合，
這是未優化的

 1 class Solution {
 2 public:
 3     bool checkInclusion(string s1, string s2) {
 4         int n = s1.length(), m = s2.length();
 5         if (n > m) {
 6             return false;
 7         }
 8         vector<int> cnt1(26), cnt2(26);
 9         for (int i = 0; i < n; ++i) {
10             ++cnt1[s1[i] - 'a'];
11             ++cnt2[s2[i] - 'a'];
12         }
13         if (cnt1 == cnt2) {
14             return true;
15         }
16         for (int i = n; i < m; ++i) {
17             ++cnt2[s2[i] - 'a'];
18             --cnt2[s2[i - n] - 'a'];
19             if (cnt1 == cnt2) {
20                 return true;
21             }
22         }
23         return false;
24     }
25 };

這是優化的

 1 class Solution {
 2 public:
 3     bool checkInclusion(string s1, string s2) {
 4         int n = s1.length(), m = s2.length();
 5         if (n > m) {
 6             return false;
 7         }
 8         vector<int> cnt(26);
 9         for (int i = 0; i < n; ++i) {
10             --cnt[s1[i] - 'a'];
11             ++cnt[s2[i] - 'a'];
12         }
13         int diff = 0;
14         for (int c: cnt) {
15             if (c != 0) {
16                 ++diff;
17             }
18         }
19         if (diff == 0) {
20             return true;
21         }
22         for (int i = n; i < m; ++i) {
23             int x = s2[i] - 'a', y = s2[i - n] - 'a';
24             if (x == y) {
25                 continue;
26             }
27             if (cnt[x] == 0) {
28                 ++diff;
29             }
30             ++cnt[x];
31             if (cnt[x] == 0) {
32                 --diff;
33             }
34             if (cnt[y] == 0) {
35                 ++diff;
36             }
37             --cnt[y];
38             if (cnt[y] == 0) {
39                 --diff;
40             }
41             if (diff == 0) {
42                 return true;
43             }
44         }
45         return false;
46     }
47 };

想詳細了解的可以去這里https://leetcode-cn.com/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/

標籤：其他

上一篇：使用java代碼實作歸并排序

下一篇：楊輝三角Ⅱ