Posted on 2023-02-04 17:28
Uriel 閱讀(48)
評論(0) 編輯 收藏 引用 所屬分類:
字符串處理 、
閑來無事重切Leet Code 、
游標.移動窗口
給出兩個字符串s1和s2，問s1的某種排列是否是s2的子串，又一python Counter的應用，先用Counter計算s1各個字符的出現次數，然后用sliding window，s2出現在sliding window中的字符對應的Counter減1，然后判斷是否存在某個sliding window讓Counter中所有計數歸零
1 #567
2 #Runtime: 299 ms (Beats 32.65%)
3 #Memory: 14 MB(Beats 23.38%)
4
5 class Solution(object):
6 def checkInclusion(self, s1, s2):
7 """
8 :type s1: str
9 :type s2: str
10 :rtype: bool
11 """
12 cnt_s1 = Counter(s1)
13 l1 = len(s1)
14 for i in range(len(s2)):
15 if s2[i] in cnt_s1:
16 cnt_s1[s2[i]] -= 1
17 if i >= l1 and s2[i-l1] in cnt_s1:
18 cnt_s1[s2[i-l1]] += 1
19 if all([cnt_s1[i] == 0 for i in cnt_s1]):
20 return True
21 return False