1220. Count Vowels Permutation - Explanation

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10**9 + 7
        follows = {
            'a': ['e'],
            'e': ['a', 'i'],
            'i': ['a', 'e', 'o', 'u'],
            'o': ['i', 'u'],
            'u': ['a']
        }

        def dfs(i, v):
            if i == n:
                return 1

            total = 0
            for nxt in follows[v]:
                total = (total + dfs(i + 1, nxt)) % MOD
            return total

        res = 0
        for vowel in ['a', 'e', 'i', 'o', 'u']:
            res = (res + dfs(1, vowel)) % MOD

        return res

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10**9 + 7
        cache = {}
        follows = {
            'a': ['e'],
            'e': ['a', 'i'],
            'i': ['a', 'e', 'o', 'u'],
            'o': ['i', 'u'],
            'u': ['a']
        }

        def dfs(i, v):
            if i == n:
                return 1
            if (i, v) in cache:
                return cache[(i, v)]

            total = 0
            for nxt in follows[v]:
                total = (total + dfs(i + 1, nxt)) % MOD
            cache[(i, v)] = total
            return total

        res = 0
        for vowel in ['a', 'e', 'i', 'o', 'u']:
            res = (res + dfs(1, vowel)) % MOD

        return res

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10**9 + 7
        a, e, i, o, u = 0, 1, 2, 3, 4
        dp = [[0] * 5 for _ in range(n + 1)]
        dp[1] = [1, 1, 1, 1, 1]

        for j in range(2, n + 1):
            dp[j][a] = (dp[j - 1][e] + dp[j - 1][i] + dp[j - 1][u]) % MOD
            dp[j][e] = (dp[j - 1][a] + dp[j - 1][i]) % MOD
            dp[j][i] = (dp[j - 1][e] + dp[j - 1][o]) % MOD
            dp[j][o] = dp[j - 1][i] % MOD
            dp[j][u] = (dp[j - 1][i] + dp[j - 1][o]) % MOD

        return sum(dp[n]) % MOD

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10**9 + 7
        follows = [
            [1],           # 'a' -> 'e'
            [0, 2],        # 'e' -> 'a', 'i'
            [0, 1, 3, 4],  # 'i' -> 'a', 'e', 'o', 'u'
            [2, 4],        # 'o' -> 'i', 'u'
            [0]            # 'u' -> 'a'
        ]
        dp = [1] * 5

        for _ in range(2, n + 1):
            next_dp = [0] * 5
            for v in range(5):
                for nextV in follows[v]:
                    next_dp[v] = (next_dp[v] + dp[nextV]) % MOD
            dp = next_dp

        return sum(dp) % MOD

class Solution:
    MOD = 10**9 + 7

    class M:
        def __init__(self, n):
            self.a = [[0] * n for _ in range(n)]

        def __mul__(self, other):
            n = len(self.a)
            product = Solution.M(n)
            for i in range(n):
                for j in range(n):
                    for k in range(n):
                        product.a[i][k] = (product.a[i][k] + self.a[i][j] * other.a[j][k]) % Solution.MOD
            return product

    def matrixExpo(self, base, exp):
        n = len(base.a)
        result = Solution.M(n)
        for i in range(n):
            result.a[i][i] = 1
        while exp > 0:
            if exp % 2 == 1:
                result = result * base
            base = base * base
            exp //= 2
        return result

    def countVowelPermutation(self, n: int) -> int:
        follows = [
            [0, 1, 0, 0, 0],  # 'a' -> 'e'
            [1, 0, 1, 0, 0],  # 'e' -> 'a', 'i'
            [1, 1, 0, 1, 1],  # 'i' -> 'a', 'e', 'o', 'u'
            [0, 0, 1, 0, 1],  # 'o' -> 'i', 'u'
            [1, 0, 0, 0, 0]   # 'u' -> 'a'
        ]

        base = Solution.M(5)
        base.a = follows

        result = self.matrixExpo(base, n - 1)

        return sum(sum(row) for row in result.a) % self.MOD