Permutation In String

发表于 | 分类于

Permutation In String

题目描述：

给定两个字符串str1和str2，要求判断str2中是否包含着str1的任意排列。

例子：

具体描述可以看LeetCode567

解题思路：

这题主要的难点是克服全排列这个问题。对于字符串的全排列我们知道，同一个字符串的所有全排列得到的哈希表是一致的；利用这个为突破口，我们首先记录下str1的哈希表，然后在str2中构建一个和str1一样大的窗口，通过不断移动窗口和判断窗口中的哈希表是否和str1的哈希表一致即可判断其是否包含了str1的排列。

代码如下：

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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size())
            return false;
        // 当str1的长度大于str2的时候肯定不符合条件
        vector<int> v1(26, 0);
        vector<int> v2(26, 0);
        // 用数组来作为哈希表的构建
        for (int i = 0; i < s1.size(); i++){
            v1[s1[i] - 'a']++;
        }
        //生成str1的哈希表
        for (int j = 0; j < s1.size(); j++){
            v2[s2[j] - 'a']++;
        }
        //生成str2前和str1长度一致的哈希表
        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;  
    }
};