Анонимное письмо из журнала

Анонимное письмо из журнала

Описание

Эта задача проверяет, можно ли составить письмо, используя символы из журнала. Каждый символ из журнала можно использовать только один раз. Это требует подсчёта частоты символов в обоих строках и сравнения их.

Решение 1: С использованием Counter из collections

from collections import Counter

def can_compose(letter, magazine):
    letter_count = Counter(letter)
    magazine_count = Counter(magazine)
    
    for char, count in letter_count.items():
        if magazine_count[char] < count:
            return False
    
    return True

print(can_compose("hello", "ehllo world"))  # True
print(can_compose("hello", "world"))         # False

Решение 2: Компактный способ с Counter

from collections import Counter

def can_compose(letter, magazine):
    return not (Counter(letter) - Counter(magazine))

print(can_compose("hello", "ehllo world"))  # True
print(can_compose("hello", "world"))         # False

Решение 3: Ручной подсчёт через словарь

def can_compose(letter, magazine):
    if len(letter) > len(magazine):
        return False
    
    char_count = {}
    
    for char in magazine:
        char_count[char] = char_count.get(char, 0) + 1
    
    for char in letter:
        if char not in char_count or char_count[char] == 0:
            return False
        char_count[char] -= 1
    
    return True

print(can_compose("hello", "ehllo world"))  # True
print(can_compose("hello", "world"))         # False

Решение 4: С использованием defaultdict

from collections import defaultdict

def can_compose(letter, magazine):
    char_count = defaultdict(int)
    
    for char in magazine:
        char_count[char] += 1
    
    for char in letter:
        if char_count[char] <= 0:
            return False
        char_count[char] -= 1
    
    return True

Решение 5: Оптимизация по памяти для ASCII

def can_compose(letter, magazine):
    if len(letter) > len(magazine):
        return False
    
    char_count = [0] * 256
    
    for char in magazine:
        char_count[ord(char)] += 1
    
    for char in letter:
        if char_count[ord(char)] == 0:
            return False
        char_count[ord(char)] -= 1
    
    return True

Тестирование

def test_can_compose():
    assert can_compose("hello", "ehllo world") == True
    assert can_compose("hello", "world") == False
    assert can_compose("a", "b") == False
    assert can_compose("", "anything") == True
    assert can_compose("abc", "abc") == True
    assert can_compose("aab", "ab") == False
    assert can_compose("aab", "baa") == True
    assert can_compose("aa", "ab") == False
    assert can_compose("aa", "aab") == True
    print("All tests passed!")

test_can_compose()

Рекомендуемое решение для интервью

from collections import Counter

def can_compose(letter: str, magazine: str) -> bool:
    return not (Counter(letter) - Counter(magazine))

Это решение является самым элегантным и питоническим. Оно использует встроенные возможности Python и демонстрирует хорошее понимание библиотеки collections. Альтернативное решение с ручным подсчётом тоже приемлемо и показывает понимание алгоритма.