Finding a permutation of one string in another: Xor solution 奇怪的行为

Question

我正在解决以下问题：

我受到 the first answer to this question 的启发，提出了一个解决方案，该解决方案利用 XOR（恒等式、交换式和自逆）的一些属性在 O(n) 时间和 O(1 ) space.

def checkInclusion(s1: str, s2: str) -> bool:
    # Checks for permutation of s1 inside of s2.
    # Xor's all of the characters in a s1-length window of s2
    # If xor_product = 0 --> permutation identified
    # Relies on properties of xor to find answer: identity, communtative, and self-inverse
    xor_product = 0
    for i in range(0, len(s2) - len(s1) + 1):
        s1_index = 0
        for j in range(i, i + len(s1)):
            xor_product = xor_product ^ ord(s1[s1_index]) ^ ord(s2[j])
            s1_index += 1
        if xor_product == 0: return True
        xor_product = 0
    return False

此解决方案适用于大多数输入，但在 s1 = "kitten" 和 s2 = "sitting" 时失败。这个解决方案在概念上有缺陷吗？如果是这样，那又如何呢？如果不是，那么错误是什么？诚然，我对编码面试风格的问题不熟悉。感谢所有帮助。

Answer 1

是的，异或方法有缺陷。

这是一种简单的散列，但对于不同的字符串，此散列可能是相同的（考虑 6^7=1 和 3^2=1）。如果异或哈希重合，您需要使用其他方法检查真正的相似性 - 例如，直接比较排序的字符串和子字符串，但这种方式不适合竞赛案例 - 具有多个相同哈希的特殊测试会导致工作缓慢，最坏情况时间太大。

相反，您可以利用 dictionary/counter 的方法。为每个新项目和离开滑动的项目更新计数器 window 并检查计数器的所有条目是否具有与示例相同的计数。

P.S。保持 NumberOfGoodCounters 值有助于避免在每一步检查所有计数器。

Finding a permutation of one string in another: Xor solution 奇怪的行为

Finding a permutation of one string in another: Xor solution strange behavior

python

algorithm

xor

bitwise-xor