LeetCode: 567. Permutation in String

发表于 | 分类于

题目描述

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

1
2
3
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

1
2
Input:s1= "ab" s2 = "eidboaoo"
Output: False

使用一个hashMap存放s1中的字符，用字符作为键，出现的次数作为值。

然后使用一个长度为s1.length()的窗口在s2上滑动，并且记录窗口中的字符串的所有字符组成的hashMap2。在滑动的同时对hashMap2进行动态的更改，然后每一次滑动都进行一次比较，如果hashMap与hashMap2中的键和值都相同，则返回True，如果到窗口滑动结束后都没有匹配，则返回False。

代码实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
private:
    bool checkMap(unordered_map<char, int> map1, unordered_map<char, int> map2) {
        for (auto it = map1.begin(); it != map1.end(); it++) {
            char item = it->first;
            if (map2.find(item) == map2.end() || map2[item] != map1[item]) {
                return false;
            }
        }
        return true;
    }

public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        unordered_map<char, int> map1;
        unordered_map<char, int> map2;
        for (int i=0; i<s1.length(); i++) {
            if (map1.find(s1[i]) == map1.end()) {
                map1[s1[i]] = 1;
            } else {
                ++map1[s1[i]];
            }
        }

        for (int i=0; i<s1.length(); i++) {
            if (map2.find(s2[i]) == map2.end()) {
                map2[s2[i]] = 1;
            } else {
                ++map2[s2[i]];
            }
        }

        for (int i=s1.length(); i<=s2.length(); i++) {
            if (checkMap(map1, map2)) {
                return true;
            }

            if (i == s2.length()) {
                return false;
            }

            if (map2[s2[i-s1.length()]] > 1) {
                --map2[s2[i-s1.length()]];
            } else {
                map2.erase(s2[i-s1.length()]);
            }

            if (map2.find(s2[i]) != map2.end()) {
                ++map2[s2[i]];
            } else {
                map2[s2[i]] = 1;
            }
        }
        return false;
    }
};