Как реализовать задачу на пайтоне?

Question

[grazer]

Имеется следующая задача:
Даны 2 слова.определить можно ли из букв первого из них получить второе.рассмотреть 2 варианта:
1) повторяющиеся буквы второго слова могут в первом слове не повторяться
2) каждая буква второго слова должна входить в первое слово столько же раз сколько и во второе

Помогите с её реализацией

Answer 1

[Andrey Dugin]

Решение первого варианта:

word1 = 'aabc'
word2 = 'aabacdff'

if any(word2.count(letter) < word1.count(letter) for letter in set(word1)):
    option = 'нельзя'
else:
    option = 'можно'

print(f'Первое слово {option} составить из букв второго')

Ещё эффективнее будет через Counter (обратите внимание на редкое использование unary minus):

from collections import Counter

counter = Counter(word2)
counter.subtract(word1)

option = ('можно', 'нельзя')[bool(-counter)]

print(f'Первое слово {option} составить из букв второго')

Со вторым вариантом задачи разберитесь сами, модифицируя код.

Answer 2

[FasterTans]

1. Разбиваете первое слово побуквенно.
2. Итерируетесь по второму слову
2.1 Каждую текущию букву, проверяете, есть ли она в массиве из п.1. Если есть - хорошо, Если нету - выкидываете ошибку.
2.2 Для вашего второго пунка, после нахождения буквы удаляете ее из массива.

Answer 3

[kurrbanov]

Решение за O(n + k), n - длина первой строки, k - длина второй строки:

Создадим словарь, в котором будем хранить количество вхождений каждой из букв первого слова. Например, "hello", будет представлено в словаре:
{
'h' : 1,
'e' : 1,
'l' : 2,
'o' : 1
}

Далее просто пробегаемся по второму слову и проверяем, есть ли текущая буква в словаре. Если нет, то такое слово составить невозможно. Есть есть, то просто вычитаем у значения буквы в словаре единицу. Если не можем вычесть(не хватает букв в первом слове), то ответ тоже нет.

s1 = str(input())
s2 = str(input())

d = dict()

for i in range(len(s1)):
    if s1[i] not in d:
        d[s1[i]] = 1
    else:
        d[s1[i]] += 1


def check():
    for i in range(len(s2)):
        if s2[i] not in d:
            return "NO"
        if d[s2[i]] - 1 >= 0:
            d[s2[i]] -= 1
        else:
            return "NO"

    return "YES"


print(check())

Comments

[Andrey Dugin]

Отличный Delphi style. Зачем здесь Python?

[kurrbanov]

Andrey Dugin, а что с моим решением не так?

[Andrey Dugin]

JustNick, неудачный алгоритм, плохой код. Нечитаемый, без очевидных названий переменных, и слишком много лишних телодвижений. Не надо так делать. На Python так не пишут. Python - краткий и лаконичный язык. Правильный код на нём всегда очень элегантен.

[kurrbanov]

Andrey Dugin, с чистотой кода согласен; не старался писать лаконично с красивым названием переменных. Но вот на счёт алгоритма не соглашусь, поправьте, если не так. Линейная скорость работы, как ни крути.

[Andrey Dugin]

JustNick, вы в check() повторно проверяете уже проверенные буквы, если они встречаются в слове несколько раз. Ничего не смущает?) А итерация по индексам зачем, если есть конструкция for letter in word?