1220. Count Vowels Permutation

LeetCode оригинал: C# #array #backtracking #csharp #leetcode #string

LeetCode Static

: 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".

C# решение

сопоставлено/оригинал

public class Solution {
    public int CountVowelPermutation(int n) {
        const int MOD = 1000000007;
        var a = new long[n];
        var e = new long[n];
        var i = new long[n];
        var o = new long[n];
        var u = new long[n];
        a[0] = 1;
        e[0] = 1;
        i[0] = 1;
        o[0] = 1;
        u[0] = 1;
        for (int k = 1; k < n; k++) {
            a[k] = (e[k - 1] + i[k - 1] + u[k - 1]) % MOD;
            e[k] = (a[k - 1] + i[k - 1]) % MOD;
            i[k] = (e[k - 1] + o[k - 1]) % MOD;
            o[k] = i[k - 1] % MOD;
            u[k] = (i[k - 1] + o[k - 1]) % MOD;
        }
        return (int)((a[n - 1] + e[n - 1] + i[n - 1] + o[n - 1] + u[n - 1]) % MOD);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountVowelPermutation(int n) {
        const int MOD = 1000000007;
        var a = new long[n];
        var e = new long[n];
        var i = new long[n];
        var o = new long[n];
        var u = new long[n];
        a[0] = 1;
        e[0] = 1;
        i[0] = 1;
        o[0] = 1;
        u[0] = 1;
        for (int k = 1; k < n; k++) {
            a[k] = (e[k - 1] + i[k - 1] + u[k - 1]) % MOD;
            e[k] = (a[k - 1] + i[k - 1]) % MOD;
            i[k] = (e[k - 1] + o[k - 1]) % MOD;
            o[k] = i[k - 1] % MOD;
            u[k] = (i[k - 1] + o[k - 1]) % MOD;
        }
        return (int)((a[n - 1] + e[n - 1] + i[n - 1] + o[n - 1] + u[n - 1]) % MOD);
    }
}

Java решение

сопоставлено/оригинал

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;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 1000000007
        a = [0] * n
        e = [0] * n
        i = [0] * n
        o = [0] * n
        u = [0] * n
        
        a[0] = e[0] = i[0] = o[0] = u[0] = 1
        
        for k in range(1, n):
            a[k] = (e[k - 1] + i[k - 1] + u[k - 1]) % MOD
            e[k] = (a[k - 1] + i[k - 1]) % MOD
            i[k] = (e[k - 1] + o[k - 1]) % MOD
            o[k] = i[k - 1] % MOD
            u[k] = (i[k - 1] + o[k - 1]) % MOD
        
        return (a[n - 1] + e[n - 1] + i[n - 1] + o[n - 1] + u[n - 1]) % MOD

Algorithm

Инициализация массивов и начальных условий:

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

Установите первый элемент в каждом массиве равным 1, так как для строк длиной 1 существует только одна возможная строка для каждой гласной.

Заполнение массивов в соответствии с правилами:

Проходите по длине строки от 1 до n.

Обновляйте значения массивов, следуя правилам для каждой гласной, учитывая предыдущие значения.

Суммирование и возврат результата:

Возьмите сумму последних элементов всех пяти массивов.

Верните результат по модулю 10^9 + 7.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.