不正确的滑动 window 算法（在 python 中）

Question

在尝试这个问题时：https://leetcode.com/problems/permutation-in-string/

"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."

我想出了一个滑动 window 解决方案，但我不想使用额外的散列 table 来跟踪当前 window 中的字母。我正在努力弄清楚为什么它不正确。

此示例失败："trinitrophenylmethylnitramine" "dinitrophenylhydrazinetrinitrophenylmethylnitramine"

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        
        s1_ht = {}
        for char in s1:
            if char in s1_ht:
                s1_ht[char] += 1
            else:
                s1_ht[char] = 1
        
        start = 0
        counter = len(s1_ht)
        
        for i in range(0, len(s2), 1):
                
            if s2[i] in s1_ht:
                s1_ht[s2[i]] -= 1
                if s1_ht[s2[i]] == 0:
                    counter -= 1
            
            if i - start + 1 == len(s1):
                    
                if counter == 0:
                    return True
                
                if s2[start] in s1_ht:
                    s1_ht[s2[start]] += 1
                    if s1_ht[s2[start]] > 0:
                        counter += 1
                        
                start += 1
        
        
        return False

Answer 1

很好的解决方案。但是这里有个小错误：

if s1_ht[s2[start]] > 0:
   counter += 1

在这些代码行中，尽管 s1_ht[ s2[start] ] 在递增之前不为零，但您递增了计数器。让我用一个例子来解释。假设s1_ht['t'] = 4。然后你找到s2[start] = 't'。因此，您递增 s1_ht['t'] 并将其设置为 5。但是随后您递增了导致错误的计数器。您不应该增加计数器，因为它已经覆盖字符 't'。用这个交换那行：

if s1_ht[s2[start]] == 1:   # just before the incrementation, it was zero
   counter += 1

它在我的机器上以 61 毫秒的运行时间和 14 MB 的内存通过了 Leetcode 测试用例。

不正确的滑动 window 算法（在 python 中）

Incorrect sliding window algorithm (in python)

python

algorithm

sliding-window