Как оптимальнее по времени проверить, является ли множество подмножеством?

Question

Как оптимальнее по времени проверить, является ли множество подмножеством?

Рейтинг: 1Ответов: 3Опубликовано: 13.04.2023

Необходимо написать функцию, которая проверяет можно ли из строки s1 сделать строку s2. Примеры:

scramble('rkqodlw', 'world') ==> True
scramble('cedewaraaossoqqyt', 'codewars') ==> True
scramble('katas', 'steak') ==> False

А вот мой код:

def scramble(s1, s2):
    result = True
    for i in s2:
        if s1.count(i) < s2.count(i) or i not in s1:
            result = False
    return result

Проблема в том, что он выходит за рамки времени выполнения задачи.

Главный вопрос: Что и как можно поменять, чтобы он работал быстрее?

python алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 7Принят

collections.Counter считает символы строки и складывает в словарь. На этих словарях определён порядок - первый словарь "больше либо равен" второму если все счётчики в первом словаре "больше либо равны" соответствующим счётчикам во втором.

@>>> import collections
@>>> c1 = collections.Counter('rkqodlw')
@>>> c1
Counter({'r': 1, 'k': 1, 'q': 1, 'o': 1, 'd': 1, 'l': 1, 'w': 1})
@>>> c2 = collections.Counter('world')
@>>> c2
Counter({'w': 1, 'o': 1, 'r': 1, 'l': 1, 'd': 1})
@>>> c1 >= c2
True

Работает это за линейное время - грубо говоря, быстрее не бывает.

import collections


def scramble(s1, s2):
    return collections.Counter(s1) >= collections.Counter(s2)


print(scramble('rkqodlw', 'world'))
print(scramble('cedewaraaossoqqyt', 'codewars'))
print(scramble('katas', 'steak'))

Answer 2

▲ 3

Можно посчитать буквы и понять, содержит ли одно слово в себе другое.

Я так понял, у вам латинские маленькие буквы в словах, потому я просто массив на 26 элементов использую для подсчета. Если у вас больше вариантов букв, замените массив на хештаблицу.

Я на C# пишу, но тут 5 строчек, переведете сами их на питон.

Итак, что мы делаем: для первого слова вы добавляем в счетчики, для второго - вычитаем, потом смотрим, если есть отрицательные счетчики, значит во втором слове каких то букв больше, чем в первом. Всё.

Код:

bool IsScrumble(string s1, string s2)
{
    var letters = new int[26];
    foreach (var c in s1) letters[c - 'a']++;
    foreach (var c in s2) letters[c - 'a']--;
    foreach (var item in letters) if (item < 0) return false;
    return true;
}

Проверка:

Console.WriteLine(IsScrumble("rkqodlw", "world"));
Console.WriteLine(IsScrumble("cedewaraaossoqqyt", "codewars"));
Console.WriteLine(IsScrumble("katas", "steak"));

Вывод:

True
True
False

Answer 3

▲ 0

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

Как оптимальнее по времени проверить, является ли множество подмножеством?

Ответы