Permutation In String

发表于 | 分类于

Permutation In String

题目描述：

给定两个字符串s1和s2要求判断s2中是否包含着s1的排列组合子串。

例子：

具体描述见LeetCode567

解题思路：

本题中主要的思路是如何判断其存在排列组合的子串。这边主要利用了数组来保存字符串的信息。在遍历s2的子串过程中不断判断和s1的数组信息是否相同即可。需要注意的是在遍历s2的时候我们需要删除被遗弃的字符的信息，增加遍历字符的信息。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size())
            return false;
            //如果s1要长于s2即不可能存在
        vector<int> v1(26, 0);
        vector<int> v2(26, 0);
        //用两个数组保存信息
        for (int i = 0; i < s1.size(); i++){
            v1[s1[i] - 'a']++;
        }
        //保存s1的信息
        for (int j = 0; j < s1.size(); j++){
            v2[s2[j] - 'a']++;
        }
        //遍历和s1相同长度的子串信息
        if (v1 == v2) return true;
        //相同的情况下直接返回
        for (int i = s1.size(); i < s2.size(); i++){
            v2[s2[i] - 'a']++;
            v2[s2[i - s1.size()] - 'a']--;
            //移位改变当前数组中的信息
            if (v1 == v2)
                return true;
            //判断是否相等
        }
        return false;
        
    }
};