Graph

1220. Count Vowels Permutation

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

• Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')

• Each vowel 'a' may only be followed by an 'e'.

• Each vowel 'e' may only be followed by an 'a' or an 'i'.

• Each vowel 'i' may not be followed by another 'i'.

• Each vowel 'o' may only be followed by an 'i' or a 'u'.

• Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

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

1-D array

def countVowelPermutation(self, n: int) -> int:
    a, e, i, o, u = 1, 1, 1, 1, 1
    
    for _ in range(n - 1):
        a,e,i,o,u = e + i + u, a + i, e + o, i, i + o
    return (a + e + i + o + u) % (10**9 + 7)