前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters.

Think

給兩個string(s1&s2)，如果s1的所有排列組合中有出現在s2中，救回傳True；如果沒有，則回傳否。

• 首先判斷是否s1的長度能包含在s2中
• 再來，先初始化s1_dict與s2_dict~
  • 這邊s2_dict存入的字母出現頻率是只有s2從index: 0開始到跟s1一樣長度的substring
• 比較s1_dict和s2_dict中有哪些字母的出現頻率是一樣的~有的話，check+1
• Init check完就先檢查一下check是不是26，因為有可能第一個s2的window中就出現s1的其中一種排列組合。

Main while loop

• 因為ptr為0的時候，已經先處理完了，所以while每次的第一行就先移動ptr到下一格(移動window)。

• MINUS Part:

  • 因為每次只移動一格，所以前一個的ptr的字母一定會不見，所以s2_dict先把前一個的ptr的字母的出現頻率-1
  • 接著，我們才來判斷s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check+1
  • 不同的話，另外再判斷原來s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check-1；不同的話，因為本來check就減過就不用管他了~

• PLUS Part:

  • 同樣地，因為每次只移動一格，所以一定會增加ptr+len(s1)的字母，所以s2_dict先把ptr+len(s1)的字母的出現頻率+1
  • 接著，跟上面一樣，我們才來判斷s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check+1
  • 不同的話，另外再判斷原來s1_dict和s2_dict中ptr-1的字母的出現頻率是否相同，相同的話，check-1；不同的話，因為本來check就減過就不用管他了~

• Return Part:

  • 如果某一次check是26，表示這次s2的window是s1的排列組合，回傳True。
  • 如果ptr+len(s1)已經大於len(s2)，表示已經跑完啦~
  • while都跑完還是沒有，就直接回傳False~

Code

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        ptr = 0
        s1_dict = {}
        s2_dict = {}
        check = 0
        
        if len(s1) > len(s2):
            return False
        
        for index in range(len(s1)):
            s1_dict[s1[index]] = 1 + s1_dict.get(s1[index], 0)
            s2_dict[s2[ptr+index]] = 1 + s2_dict.get(s2[ptr+index], 0)
        
        # init check
        for letter in range(ord('a'), ord('z') + 1):
            if s1_dict.get(chr(letter), 0) == s2_dict.get(chr(letter), 0):
                check += 1
        
        # print("Init Check: ", check)
        if check == 26:
                return True
        
        while ptr+len(s1) < len(s2):
            ptr += 1
            
            # print("Window: ", s2[ptr:ptr+len(s1)])
            
            # MINUS previous ptr
            s2_dict[s2[ptr-1]] -= 1
            # 如果刪掉前一個s2[ptr]後，s2[ptr]在這個window中跟在s1中s2[ptr]這個字母的出現頻率一樣
            # 就把check+1，表示這個字母在s1跟s2出現頻率一樣
            if s1_dict.get(s2[ptr-1], 0) == s2_dict[s2[ptr-1]]:
                check += 1
            else:
                if s1_dict.get(s2[ptr-1], 0) == s2_dict[s2[ptr-1]] + 1:
                    check -= 1
            
            # print("After minus => \ns2_dict: ", s2_dict)
            
            # print("Check: ", check, "\n")
            
            # PLUS ptr+len(s2)
            s2_dict[s2[ptr+len(s1)-1]] = 1 + s2_dict.get(s2[ptr+len(s1)-1], 0)
            if s1_dict.get(s2[ptr+len(s1)-1], 0) == s2_dict.get(s2[ptr+len(s1)-1], 0):
                check += 1
            else:
                if s1_dict.get(s2[ptr+len(s1)-1], 0) == s2_dict[s2[ptr+len(s1)-1]] - 1:
                    check -= 1
            
            # print("After plus => \ns2_dict: ", s2_dict)
            # print("Check: ", check, "\n\n\n")
            
            if check == 26:
                return True
        return False

Submission

今天就到這邊啦~
大家明天見