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)