567.md

Permutation in String

Description

link

---

Solution

• set p1 p2 represent the permutation of string
• using slide window to compare two array

---

Code

O(n * m)

class Solution:
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        p1 = [0] * 26
        p2 = [0] * 26
        
        for x in s1:
            p1[ord(x) - ord('a')] += 1
            
        for i in range(len(s2)):
            p2[ord(s2[i]) - ord('a')] += 1
            if i > len(s1) - 1:
                p2[ord(s2[i - len(s1)]) - ord('a')] -= 1
            if p1 == p2:
                return True
        
        return False