[Leetcode] Problem 567 - Permutation in String

Posted on | In ,

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

No.1

Input: s1 = “ab” s2 = “eidbaooo”

Output: True

Explanation: s2 contains one permutation of s1 (“ba”).

No.2

Input:s1= “ab” s2 = “eidboaoo”

Output: False

Constraints

  • The input strings only contain lower case letters.
  • The length of both given strings is in range [1, 10,000].

Code

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
public boolean checkInclusion(String s1, String s2) {
    int l1 = s1.length();
    int l2 = s2.length();
    int[] count = new int[26];

    if (l1 > l2)
        return false;

    for (char ch : s1.toCharArray())
        count[ch - 'a'] += 1;

    for (int i = 0; i < l2; i++) {
        count[s2.charAt(i) - 'a'] -= 1;

        if (i >= l1)
            count[s2.charAt(i - l1) - 'a'] += 1;

        if (match(count))
            return true;
    }

    return false;
}

private boolean match(int[] count) {
    for (int c : count) {
        if (c != 0)
            return false;
    }

    return true;
}