Skip to content

Latest commit

 

History

History
96 lines (54 loc) · 6.77 KB

count-vowels-permutations.md

File metadata and controls

96 lines (54 loc) · 6.77 KB
Raw

1220. Count Vowels Permutations

Задача

Дано натуральное число n и следущие правила формирования строки длины n :

  • Состоит только из символов: 'a', 'e', 'i', 'o', 'u';
  • За a может сделовать только e;
  • За e может следовать a или i;
  • За i не может следовать i;
  • За o может следовать i или u;
  • За u может следовать только a.

Нужно сказать сколько существует таких строк длины n .

Задача на LeetCode

Вопросы

Начинаем, как обычно, с вопросов чтобы понять о чем задача и какие есть ограничения.

  1. Ограничения задачи:

    • В каких пределах может быть n ?

      Натуральные числа 1 <= n <= 2 * 10^4

  2. Ожидаемый результат:

    • Кажется, для 2 * 10^4 число комбинацией может получиться очень большим. Нужно ли использовать длинную арифметику или можно выдать результат по модулю?

    По модулю 1e9 + 7

Примеры

  1. Пример 1:

n = 1, ответ: 5

Строки: "a", "e", "i" , "o" and "u"

  1. Пример 2:

n = 2, ответ: 10

Строки: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua"

Наивный подход

Что является наивным подходом в данной задаче? Можно построить все строки длины n по описанным правилам и посчитать их количество. Представим, что n относительно небольшое, скажем не более 5, тогда это вполне имеет смысл.

Полезно посмотреть на сам принцип "генерации строк по правилам".

Удобно воспользоваться рекурсией.

  • На первом уровне у нас есть пять букв
    • К каждой из них можно пристегнуть другую по определенным правилам (сделать рекурсивный вызов)
    • Когда мы добираемся до строки длины n — кладем строку в ответ, заканчиваем рекурсию (базовый случай)

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

Для n ~ 10^4 такое решение не пойдет, потому что количество строк растет экспоненциально.

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

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

Динамическое программирование

Здесь мы приходим к динамическому программированию. Цель — избавиться от экспоненты в сложности.

Каждый следующий уровень в этом дереве строится на основе предыдущего, то есть количество узлов на следующем уровне будет как-то выражаться через количество узлов на предыдущем уровне (если только правила не меняются от уровня к уровню). Собственно, нам нужно найти это как-то - рекуррентное соотношение.

Если мы знаем количество префиксов длины i - 1 , которые заканчиваются в определенной букве, то можно сказать:

  • dp[i]['a'] = dp[i − 1]['e'] (За a может сделовать только e)
  • dp[i]['e'] = (dp[i − 1]['a'] + dp[i − 1]['i']) (За e может следовать a или i)
  • dp[i]['i'] = (dp[i − 1]['a'] + dp[i − 1]['e'] + dp[i − 1]['o'] + dp[i − 1]['u']) (За i могут следовать все буквы, кроме i)
  • dp[i]['o'] = (dp[i − 1]['i'] + dp[i − 1]['u']) (За o может следовать i или u)
  • dp[i]['u'] = dp[i − 1]['a'] (За u может следовать только a)

Обращение по символу условное, для наглядности. Логично использовать индекс 0 <= j < 5 под каждую буквы.

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

В итоге, получаем линейную сложность 🙌

P. S. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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