🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1220. Count Vowels Permutation
Сложность: hard
Дано целое число n, ваша задача состоит в том, чтобы посчитать, сколько строк длины n можно сформировать по следующим правилам:
Каждый символ является строчной гласной буквой ('a', 'e', 'i', 'o', 'u')
Каждая гласная 'a' может быть только перед 'e'.
Каждая гласная 'e' может быть только перед 'a' или 'i'.
Каждая гласная 'i' не может быть перед другой 'i'.
Каждая гласная 'o' может быть только перед 'i' или 'u'.
Каждая гласная 'u' может быть только перед 'a'.
Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".
👨💻 Алгоритм:
1⃣Инициализация массивов и начальных условий:
Инициализируйте пять одномерных массивов размером n для хранения количества строк, оканчивающихся на каждую гласную.
Установите первый элемент в каждом массиве равным 1, так как для строк длиной 1 существует только одна возможная строка для каждой гласной.
2⃣Заполнение массивов в соответствии с правилами:
Проходите по длине строки от 1 до n.
Обновляйте значения массивов, следуя правилам для каждой гласной, учитывая предыдущие значения.
3⃣Суммирование и возврат результата:
Возьмите сумму последних элементов всех пяти массивов.
Верните результат по модулю 10^9 + 7.
😎 Решение:
class Solution {
public int countVowelPermutation(int n) {
long[] aVowelPermutationCount = new long[n];
long[] eVowelPermutationCount = new long[n];
long[] iVowelPermutationCount = new long[n];
long[] oVowelPermutationCount = new long[n];
long[] uVowelPermutationCount = new long[n];
aVowelPermutationCount[0] = 1L;
eVowelPermutationCount[0] = 1L;
iVowelPermutationCount[0] = 1L;
oVowelPermutationCount[0] = 1L;
uVowelPermutationCount[0] = 1L;
int MOD = 1000000007;
for (int i = 1; i < n; i++) {
aVowelPermutationCount[i] = (eVowelPermutationCount[i - 1] + iVowelPermutationCount[i - 1] + uVowelPermutationCount[i - 1]) % MOD;
eVowelPermutationCount[i] = (aVowelPermutationCount[i - 1] + iVowelPermutationCount[i - 1]) % MOD;
iVowelPermutationCount[i] = (eVowelPermutationCount[i - 1] + oVowelPermutationCount[i - 1]) % MOD;
oVowelPermutationCount[i] = iVowelPermutationCount[i - 1] % MOD;
uVowelPermutationCount[i] = (iVowelPermutationCount[i - 1] + oVowelPermutationCount[i - 1]) % MOD;
}
long result = 0L;
result = (aVowelPermutationCount[n - 1] + eVowelPermutationCount[n - 1] + iVowelPermutationCount[n - 1] + oVowelPermutationCount[n - 1] + uVowelPermutationCount[n - 1]) % MOD;
return (int)result;
}
}
Ставь 👍 и забирай 📚 Базу знаний
