Как можно оптимизировать поиск?

Question

Нужно, чтобы сравнивало две строки - одна с них которая слово, а вторая набор символов (с лишними символами). В результате если со второй строки можно сложить первую - возвращать True, если нет - False.

def search(s1, s2):
    return ''.join([n for n in s2 if s2.count(n) <= s1.count(n)]) == s2

Вопрос, как можно оптимизировать процес поиска, если строки могут быть больше 6к символов?

Answer 1

from collections import Counter
s1 = 'hello'
s2 = 'helol'
s3 = 'hleo'
print(Counter(s1) == Counter(s2)) # True
print(Counter(s1) == Counter(s3)) # False

Answer 2

collections.Counter поддерживает вычитание. Вычитаются значения под одинаковыми ключами (буквами), отрицательные или нулевые значения из разницы исключаются. Если после вычитания строка - набор символов останется пустой словарь, значит в наборе символов достаточно букв чтобы составить слово.

Сложность алгоритма линейная. Константа маленькая, так как почти весь код на C:

import collections

def search(s1, s2):
    return len(collections.Counter(s1) - collections.Counter(s2)) == 0

print(search('a', 'aa'))
print(search('aaa', 'aa'))
print(search('b', 'aa'))

$ python counters.py 
True
False
False

Answer 3

def search(s1, s2):
    if len(s2) > len(s1):
        return False
    s1 = iter(sorted(s1))
    s2 = sorted(s2)
    return all(el in s1 for el in s2)

Answer 4

если не использовать какие-то функции сторонних библиотек, я бы сделал бы так:

из второй строки сформировал бы словарь, где подсчитал бы кол-во каждого символа
```
 db = {}

 for letter in text_src:
     db[letter] = db.get(letter, 0) + 1
```

это должно занять O(n) + O(nlog(n)) = O(nlog(n)) времени

пройтись символами первой строки по словарю уменьшая кол-во символов и если их станет меньше 0, то все - строка не складывается
```
 for letter in text_dst:
     if db[letter] == 0:
         return False
     else:
         db[letter] -= 1

 return True
```

тут время тоже O(nlog(n))

Но можно решить задачу строго за линейное время O(n) - для этого не нужно использовать словарь, и надо использовать таблицу символов, тогда поиск нужного символа занимает O(1), т.е. максимально быстро

def check(text_dst, text_src):
    # сформировать таблицу кол-ва символов
    db = [0] * 256

    for letter in text_src:
        db[ord(letter)] += 1

    # проверить символы слова по таблице
    for letter in text_dst:
        index = ord(letter)

        if db[index] == 0:
            return False

        db[index] -= 1

    return True

БЛОГ НА HUSL

Как можно оптимизировать поиск?

Ответы (4 шт):