Finding a permutation of one string in another: Xor solution 奇怪的行为
Finding a permutation of one string in another: Xor solution strange behavior
我正在解决以下问题:
我受到 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"
时失败。这个解决方案在概念上有缺陷吗?如果是这样,那又如何呢?如果不是,那么错误是什么?
诚然,我对编码面试风格的问题不熟悉。感谢所有帮助。
是的,异或方法有缺陷。
这是一种简单的散列,但对于不同的字符串,此散列可能是相同的(考虑 6^7=1 和 3^2=1)。如果异或哈希重合,您需要使用其他方法检查真正的相似性 - 例如,直接比较排序的字符串和子字符串,但这种方式不适合竞赛案例 - 具有多个相同哈希的特殊测试会导致工作缓慢,最坏情况时间太大。
相反,您可以利用 dictionary/counter 的方法。为每个新项目和离开滑动的项目更新计数器 window 并检查计数器的所有条目是否具有与示例相同的计数。
P.S。保持 NumberOfGoodCounters
值有助于避免在每一步检查所有计数器。
我正在解决以下问题:
我受到 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"
时失败。这个解决方案在概念上有缺陷吗?如果是这样,那又如何呢?如果不是,那么错误是什么?
诚然,我对编码面试风格的问题不熟悉。感谢所有帮助。
是的,异或方法有缺陷。
这是一种简单的散列,但对于不同的字符串,此散列可能是相同的(考虑 6^7=1 和 3^2=1)。如果异或哈希重合,您需要使用其他方法检查真正的相似性 - 例如,直接比较排序的字符串和子字符串,但这种方式不适合竞赛案例 - 具有多个相同哈希的特殊测试会导致工作缓慢,最坏情况时间太大。
相反,您可以利用 dictionary/counter 的方法。为每个新项目和离开滑动的项目更新计数器 window 并检查计数器的所有条目是否具有与示例相同的计数。
P.S。保持 NumberOfGoodCounters
值有助于避免在每一步检查所有计数器。