Как можно ускорить код проверки, что из букв первой строки можно создать вторую строку?

Рейтинг: 0Ответов: 2Опубликовано: 30.05.2023

Есть две строки. Если буквы из второй строки совпадают с буквами из первой строки тогда True иначе False. Короче чтобы из букв первой строки можно было составить слово из второй строки.

def scramble(s1, s2):

    for x in s1:
        if s2.find(x) != -1:
            s2 = s2.replace(x, '', 1)
            
       
    if len(s2)==0:
        return print(True)
    else:
        return print(False)
            
scramble('rkqodlw', 'world')
python python-3.x строки
Источник: Stack Overflow на русском

Ответы

▲ 7Принят

Создаём словарь со счётчиками символов второй строки. Для каждого символа из первой уменьшаем соотв. счётчик. В конце смотрим, чтобы не осталось ненулевых счётчиков. Сложность примерно линейная O(len(s1)+len(s2))

from collections import Counter
def sc1(s1, s2):
    if len(s2) == 0:
        return True
    cnt = Counter(s2)
    for x in s1:
        if cnt[x]:
            cnt[x] -= 1
    return cnt.most_common(1)[0][1]==0

Ещё проще, как подсказал extrn, выполнить сравнение Counter - для версии Python >= 3.10

def scr(s1, s2):
    return Counter(s2) <= Counter(s1)

Вариант с сортировкой, сложность O(len1*log(len1)+len2*log(len2))

def sc2(s1, s2):
    l1 = sorted(list(s1))
    l2 = sorted(list(s2))
    i1, i2 = 0, 0
    while i1 < len(l1) and i2 < len(l2):
        if l1[i1]==l2[i2]:
            i1 += 1
            i2 += 1
        elif l1[i1] > l2[i2]:
            return False
        else:
            i1 += 1
    return i2 == len(l2)
▲ 2

Для более старых версий питона можно вычесть Counter-ы слов и проверить, что получилась пустая коллекция:

from collections import Counter

def scramble(s1, s2):
    return not (Counter(s2) - Counter(s1))

print(scramble('приветствие', 'твист'))
print(scramble('приветствие', 'истец'))

Вывод:

True
False