python - 寻找一个字符串在另一个字符串中的排列：异或解奇怪的行为

Question

我正在解决以下问题：

我受到这个问题的第一个答案的启发，想出了一个解决方案，该解决方案利用 XOR（恒等、交换和自逆）的一些属性在 O(n) 时间和 O(1) 空间中工作。

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"。这个解决方案在概念上是否存在缺陷？如果是这样，那怎么办？如果不是，那是什么错误？诚然，我对编码面试风格问题很陌生。所有帮助表示赞赏。

标签： pythonalgorithmxorbitwise-xor

Answer 1

是的，异或方法是有缺陷的。

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

相反，您可以利用字典/计数器的方法。为每个新项目和离开滑动窗口的项目更新计数器，并检查计数器的所有条目是否与样本具有相同的计数。

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