567 Permutation in String

567. Permutation in String​
1. Question
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
Input: s1 = "ab" s2 = "eidbaooo"
2
​
3
Output: True
4
​
5
Explanation: s2 contains one permutation of s1 ("ba").
Copied!
Example 2:
1
Input: s1= "ab" s2 = "eidboaoo"
2
​
3
Output: False
Copied!
2. Implementation
(1) Two Pointers + Hash
1
class Solution {
2
    public boolean checkInclusion(String s1, String s2) {
3
        if (s1.length() > s2.length()) {
4
            return false;
5
        }
6
​
7
        int[] map = new int[256];
8
​
9
        for (char c : s1.toCharArray()) {
10
            ++map[c];
11
        }
12
​
13
        int end = 0, start = 0, count = s1.length();
14
​
15
        while (end < s2.length()) {
16
            if (map[s2.charAt(end)] > 0) {
17
                --count;
18
            }
19
            --map[s2.charAt(end)];
20
            ++end;
21
​
22
            if (end - start - 1 == s1.length()) {
23
                if (map[s2.charAt(start)] >= 0) {
24
                    ++count;
25
                }
26
                ++map[s2.charAt(start)];
27
                ++start;
28
            }
29
​
30
            if (count == 0) {
31
                return true;
32
            }
33
        }
34
        return false;
35
    }
36
}
Copied!
3. Time & Space Complexity
Two Pointers + Hash: 时间复杂度O(n), 空间复杂度O(1)

532 K-diff Pairs in an Array

611 Valid Triangle Number

Last modified 2yr ago

Copy link

Contents

567. Permutation in String

1. Question

2. Implementation

3. Time & Space Complexity

567. Permutation in String​

1. Question

2. Implementation

3. Time & Space Complexity

567. Permutation in String