Записка о выкупе

Постановка задачи

ransomNote = "a", magazine = "b"

false

ransomNote = "aa", magazine = "ab"

false

ransomNote = "aa", magazine = "aab"

true

Решение

Представим, что есть похититель, который хочет отправить анонимную записку о выкупе. Чтобы его почерк не узнали, он вырезает буквы из журнала. Есть две строки: ransomNote - текст записки и magazine - текст в журнале. Задача в том, чтобы проверить, хватит ли букв из журнала magazine, чтобы составить записку ransomNote при условии, что каждую букву из журнала можно использовать только один раз.

Если рассуждать максимально просто, мы можем для каждой буквы из записки делать поиск в журнале. Если нашли, то "вырезаем" ее из журнала, чтобы не использовать дважды.

1. Идем циклом по строке ransomNote.
2. Для каждого текущего символа запускаем поиск в строке magazine.
   • Если символ найден, "удаляем" его из magazine.
   • Если символ не найден, возвращаем false, так как составить записку не получится.
3. Если цикл завершился успешно, возвращаем true.

Давайте теперь оценим такое решение по сложности. Для каждой из n букв записки ransomNote мы выполняем поиск и удаление, которые в худшем случае потребуют прохода по всей длине строки magazine. Если обозначить длину строки magazine за m, то сложность такого решения можно записать как O(n * m). Если в записке 1000 букв и в журнале 1000, это будет около миллиона операций. По сути, это квадратичная сложность, и такое решение не годится, его нужно оптимизировать.

При проверке каждой буквы из записки мы снова и снова повторяем проход по строке magazine. Эти повторные проходы и приводят к лишней работе и неэффективности. Если бы мы могли избежать этих повторных проходов, то смогли бы значительно улучшить алгоритм. Это подсказка, что нам здесь нужна подходящая структура данных.

В таких задачах надо уметь заметить идею "инвентаризации" доступных элементов для учета их изначального количества и последующего изменения по мере использования. Давайте сгруппируем все буквы из magazine в какую-нибудь структуру данных, где для каждой буквы будем хранить ее количество, то есть частоту. Так мы сможем избежать повторных проходов по строке magazine и вместо медленного поиска по строке будем быстро узнавать из структуры данных, есть ли буква и сколько таких букв осталось.

Какая структура данных подойдет? Когда требуется отслеживать количество элементов или нужно быстро по элементу получать значение, то это намек на хеш-таблицу.

Использование хеш-таблицы для учета букв в журнале - это эффективный способ решения этой задачи.

Основные шаги:

1. Считаем буквы в журнале: проходим по строке magazine и записываем в хеш-таблицу, сколько раз встретилась каждая буква.

2. Проверяем записку: идем циклом по строке ransomNote и для каждой буквы проверяем, есть ли она в нашем "запасе" из журнала:

   • Если буквы нет или ее количество равно нулю, возвращаем false, записка не может быть составлена.
   • Если есть, уменьшаем счетчик этой буквы в таблице на единицу.

3. При завершении цикла мы прошли всю записку до конца, значит, букв нам хватило, и записка может быть составлена. Возвращаем true.

В этой задаче можно хорошо показать принцип работы хеш-таблиц. Так как алфавит допустимых символов - это строчные английские буквы, то вместо настоящей хеш-таблицы мы можем использовать массив из 26 элементов.

Если вы не знакомы с тем, как устроены хеш-таблицы, то вот главная идея: хеш-таблицу можно представлять себе как массив, в котором вместо целого числа в качестве индекса используется ключ - элемент почти любого типа данных, например буква, строка или произвольная структура данных с определенными свойствами. При чтении или записи в хеш-таблицу по ключу ключ при помощи хеш-функции переводится в индекс и далее по индексу мы можем найти нужный элемент.

Рассмотрим это подробнее на нашем примере. У нас есть массив из 26 элементов - это наша хеш-таблица. В качестве хеш-функции мы возьмем f(c) = c - 'a', которая для любой строчной английской буквы переведет ее в число от 0до25, то есть в индекс ячейки массива. По этому индексу мы сразу получаем доступ к значению, которое хранится в таблице для ключа. Для текущей задачи такая хеш-функция идеальна, так как количество возможных ключей, a, b, c, ..., x, y, z, совпадает с количеством ячеек в нашей таблице, и у нас не возникнет коллизий.

Давайте сделаем ручной прогон и увидим, как это работает на примере:

ransomNote: "abc"
magazine: "aabbc"

1. Подготовка таблицы

Мы берем пустую таблицу, то есть массив, и считаем буквы в журнале, проходя по magazine.

• Буква 'a', таблица [1, 0, 0, ...]

• Буква 'a', таблица [2, 0, 0, ...]

• Буква 'b', таблица [2, 1, 0, ...]

• Буква 'b', таблица [2, 2, 0, ...]

• Буква 'c', таблица [2, 2, 1, ...]

Итог шага: у нас есть таблица частот букв из журнала. Мы знаем, что букв a

• 2 штуки, b - 2 штуки, c - 1 штука.

2. Проверяем записку

Теперь мы берем нашу записку "abc" и проверяем каждую букву по очереди, заглядывая в таблицу.

• Буква 'a':
  • Вопрос: Есть ли 'a' в таблице и больше ли ее количество, чем 0?
  • Ответ: Да, там их 2.
  • Действие: Забираем одну. В таблице остается: [1, 2, 1, ...].

• Буква 'b':
  • Вопрос: Есть ли 'b'?
  • Ответ: Да, там их 2.
  • Действие: Забираем одну. В таблице остается: [1, 1, 1, ...].

• Буква 'c':
  • Вопрос: Есть ли 'c'?
  • Ответ: Да, она 1.
  • Действие: Забираем. В таблице остается: [1, 1, 0, ...].

3. Завершение цикла

Записка закончилась, мы ни разу не наткнулись на нехватку букв.

Результат: true - записку можно составить.

А если бы букв не хватило?

Если бы в записке была еще одна буква 'c' ("abcc"):

• Мы бы посмотрели в таблицу при проверке второй буквы 'c'. Увидели бы, что напротив 'c' стоит 0.
• Сразу бы вернули: false (буквы закончились).

Почему это эффективно?

Нам не нужно каждый раз заново пробегать по всему журналу. Мы смотрим только в одну "ячейку" таблицы, что происходит мгновенно.

Оценка сложности

Временная сложность

Мы проходим по строке magazine ровно один раз с помощью одного цикла и на каждом шаге обновляем хеш-таблицу. Операция обновления элемента в хеш-таблице в среднем занимает O(1), поэтому сложность построения таблицы получается O(m), где m - длина журнала.

Далее делаем за один цикл проверку, проходя по строке ransomNote, поэтому сложность проверки получается O(n), где n - длина записки.

Общая временная сложность: O(m + n).

Пространственная сложность

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

Код решения

Приведем код решения.

func canConstruct(ransomNote string, magazine string) bool {
    var counts [26]int
    for _, char := range magazine {
        // вычитая 'a' из символа, мы получаем индекс от 0 до 25
        counts[char-'a']++
    }
    for _, char := range ransomNote {
        index := char - 'a'
        if counts[index] == 0 {
            return false
        }
        counts[index]--
    }
    return true
}
 

Итоги

Вот основные итоги разбора этой задачи, которые пригодятся на интервью и на практике:

1. Эффективность хеш-таблиц. Используйте хеш-таблицы, чтобы избежать повторных поисков элементов.

2. Когда использовать хеш-таблицы.

   • Если нужно считать количество/частоту чего-либо.
   • Нужно мгновенно проверять существование элемента.
   • Нужно найти пары или дубликаты.
   • Требуется связать одни данные с другими (ключ-значение).

3. Сложность оптимального решения. Временная: O(m + n) - линейный проход по обеим строкам. Пространственная: O(1) или O(k) - память зависит от размера алфавита, а не от длины входных строк.

4. Главный урок задачи: "память против скорости" (Space-Time Tradeoff). Вместо того, чтобы тратить время на повторный поиск букв в журнале для каждого символа записки, что привело бы к медленной работе O(m * n), мы выделяем дополнительную память (хеш-таблицу или массив) для хранения состояния.