字符串的排列（雙指針）

新進小設(shè)計 2022-08-13 發(fā)布于北京

展開全文

先給題
給定兩個字符串 s1 和 s2，寫一個函數(shù)來判斷 s2 是否包含 s1 的排列。

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

示例1:

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

示例2:

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

注意：

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

來源：力扣（LeetCode）
鏈接：https:///problems/permutation-in-string

今天第一次，沒有看題解做出來了，時間和內(nèi)存還都可以的情況下。繼續(xù)加油！

1.暴力破解

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

2.自己想的

說一說自己的想法

（1）總體思想

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

（2）我們先來談一談左指針如何移動。

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

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

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

（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;
}
};

View Code

3.題解

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

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

 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 };

View Code

這是優(yōu)化的

 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 };