Нахождение перестановки одной строки в другую: Xor решение странное поведение - PullRequest
Новая
       39

Нахождение перестановки одной строки в другую: Xor решение странное поведение

0 голосов
/ 12 марта 2020

Я работаю над следующей проблемой:

enter image description here

Меня вдохновил первый ответ на этот вопрос в будущем решение, использующее некоторые свойства XOR (Identity, Commulative и Self-Inverse) для работы в 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". Концептуально ли это решение ошибочно? Если так, то как? Если нет, то в чем ошибка? По общему признанию, я новичок в кодировании вопросов стиля интервью. Вся помощь оценена.

1 Ответ

3 голосов
/ 12 марта 2020

Да, XOR-подход имеет недостатки.

Это просто ха sh, но этот ха sh может быть одинаковым для разных строк (рассмотрим 6 ^ 7 = 1 и 3 ^ 2 = 1). В случае совпадения xor ha sh вам необходимо проверить реальное сходство с другими средствами - например, с прямым сравнением отсортированной строки и подстроки, но этот способ не подходит для случая конкурса - специальные тесты с несколькими одинаковыми хэшами приведут к медленному В худшем случае время слишком велико.

Вместо этого вы можете использовать подход с помощью словаря / счетчика. Обновите счетчики для каждого нового элемента и для элемента, выходящего из скользящего окна, и убедитесь, что все записи счетчика имеют те же счетчики, что и образец.

Значение PS * NumberOfGoodCounters помогает избежать проверки всех счетчиков на каждом шаге.

...