permutation_in_string

View Source

 1from collections import Counter
 2
 3
 4# @leet start
 5class Solution:
 6    def checkInclusion(self, s1: str, s2: str) -> bool:
 7        """
 8        This question asks to check if `s1` or a permutation of `s1` is contained
 9        in `s2`.
10
11        Take the first example, `ab` and `eidbaooo`. `ba` is in `s2`, so this
12        is true.
13
14        Since we want any ordering of the letters from `s1` to be in a substring
15        of `s2`, we can hold a counter of `s1` and check for equality as we
16        iterate through `s2`.
17
18        The solution detailed is terse but could be optimized, since it always
19        recreates the counter.
20
21        The optimized way would be to maintain a counter and then when moving
22        to the left, remove the character that falls outside of the window and
23        adding in the new character to the counter.
24        """
25        left = Counter(s1)
26
27        width = len(s1)
28
29        for i in range(len(s2) - width + 1):
30            right = Counter(s2[i : i + width])
31            if left == right:
32                return True
33
34        return False
35
36
37# @leet end
38q = Solution().checkInclusion
39
40
41def test():
42    assert q("ab", "eidbaooo")
43    assert q("ab", "eidboaoo")
44    assert q("adc", "dcda")

class Solution: View Source

 6class Solution:
 7    def checkInclusion(self, s1: str, s2: str) -> bool:
 8        """
 9        This question asks to check if `s1` or a permutation of `s1` is contained
10        in `s2`.
11
12        Take the first example, `ab` and `eidbaooo`. `ba` is in `s2`, so this
13        is true.
14
15        Since we want any ordering of the letters from `s1` to be in a substring
16        of `s2`, we can hold a counter of `s1` and check for equality as we
17        iterate through `s2`.
18
19        The solution detailed is terse but could be optimized, since it always
20        recreates the counter.
21
22        The optimized way would be to maintain a counter and then when moving
23        to the left, remove the character that falls outside of the window and
24        adding in the new character to the counter.
25        """
26        left = Counter(s1)
27
28        width = len(s1)
29
30        for i in range(len(s2) - width + 1):
31            right = Counter(s2[i : i + width])
32            if left == right:
33                return True
34
35        return False

def checkInclusion(self, s1: str, s2: str) -> bool: View Source

 7    def checkInclusion(self, s1: str, s2: str) -> bool:
 8        """
 9        This question asks to check if `s1` or a permutation of `s1` is contained
10        in `s2`.
11
12        Take the first example, `ab` and `eidbaooo`. `ba` is in `s2`, so this
13        is true.
14
15        Since we want any ordering of the letters from `s1` to be in a substring
16        of `s2`, we can hold a counter of `s1` and check for equality as we
17        iterate through `s2`.
18
19        The solution detailed is terse but could be optimized, since it always
20        recreates the counter.
21
22        The optimized way would be to maintain a counter and then when moving
23        to the left, remove the character that falls outside of the window and
24        adding in the new character to the counter.
25        """
26        left = Counter(s1)
27
28        width = len(s1)
29
30        for i in range(len(s2) - width + 1):
31            right = Counter(s2[i : i + width])
32            if left == right:
33                return True
34
35        return False

This question asks to check if s1 or a permutation of s1 is contained in s2.

Take the first example, ab and eidbaooo. ba is in s2, so this is true.

Since we want any ordering of the letters from s1 to be in a substring of s2, we can hold a counter of s1 and check for equality as we iterate through s2.

The solution detailed is terse but could be optimized, since it always recreates the counter.

The optimized way would be to maintain a counter and then when moving to the left, remove the character that falls outside of the window and adding in the new character to the counter.

def q(s1: str, s2: str) -> bool: View Source

 7    def checkInclusion(self, s1: str, s2: str) -> bool:
 8        """
 9        This question asks to check if `s1` or a permutation of `s1` is contained
10        in `s2`.
11
12        Take the first example, `ab` and `eidbaooo`. `ba` is in `s2`, so this
13        is true.
14
15        Since we want any ordering of the letters from `s1` to be in a substring
16        of `s2`, we can hold a counter of `s1` and check for equality as we
17        iterate through `s2`.
18
19        The solution detailed is terse but could be optimized, since it always
20        recreates the counter.
21
22        The optimized way would be to maintain a counter and then when moving
23        to the left, remove the character that falls outside of the window and
24        adding in the new character to the counter.
25        """
26        left = Counter(s1)
27
28        width = len(s1)
29
30        for i in range(len(s2) - width + 1):
31            right = Counter(s2[i : i + width])
32            if left == right:
33                return True
34
35        return False

This question asks to check if s1 or a permutation of s1 is contained in s2.

Take the first example, ab and eidbaooo. ba is in s2, so this is true.

Since we want any ordering of the letters from s1 to be in a substring of s2, we can hold a counter of s1 and check for equality as we iterate through s2.

The solution detailed is terse but could be optimized, since it always recreates the counter.

The optimized way would be to maintain a counter and then when moving to the left, remove the character that falls outside of the window and adding in the new character to the counter.

def test(): View Source

42def test():
43    assert q("ab", "eidbaooo")
44    assert q("ab", "eidboaoo")
45    assert q("adc", "dcda")