1220. Count Vowels Permutation

1220. Count Vowels Permutation

 

https://youtu.be/VUVpTZVa7Ls?si=ebIzPzi9iQeVkNQa

 

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        """
        Permutation: 순열 / Permutation
        아래 규칙을 따르는 n 길이의 순열 개수 계산:
        Calculate the number of permutations of length `n` following these rules:
        - 문자열은 a, e, i, o, u로만 구성 / The string consists of only 'a', 'e', 'i', 'o', 'u'.
        - 규칙 / Rules:
          1. 'a' 뒤에는 'e'만 올 수 있음 / 'a' can only be followed by 'e'.
          2. 'e' 뒤에는 'a', 'i'만 올 수 있음 / 'e' can only be followed by 'a' or 'i'.
          3. 'i' 뒤에는 'a', 'e', 'o', 'u'가 올 수 있지만 'i'는 올 수 없음 /
             'i' can be followed by 'a', 'e', 'o', or 'u', but not by another 'i'.
          4. 'o' 뒤에는 'i', 'u'만 올 수 있음 / 'o' can only be followed by 'i' or 'u'.
          5. 'u' 뒤에는 'a'만 올 수 있음 / 'u' can only be followed by 'a'.

        바꿔 말하면: / In other words:
        - 'a'가 끝에 오려면 이전 문자로 'e', 'i', 'u'가 올 수 있음 /
          To end with 'a', the previous character must be 'e', 'i', or 'u'.
        - 'dp[j][a] = dp[j-1][e] + dp[j-1][i] + dp[j-1][u]'

        초기값 (길이 1의 문자열): / Initial state (strings of length 1):
        - dp[1][a] = 1
        - dp[1][e] = 1
        - dp[1][i] = 1
        - dp[1][o] = 1
        - dp[1][u] = 1
        """
        
        # dp[j][c]: j 길이의 문자열에서 마지막 문자가 c일 때의 가능한 문자열 수
        # dp[j][c]: Number of valid strings of length `j` where the last character is `c`.
        
        # dp 초기화: 길이 1일 때는 모든 모음이 각각 1개의 경우를 가짐
        # Initialize DP table: At length 1, each vowel has exactly 1 possible string.
        dp = [[], [1, 1, 1, 1, 1]]  # dp[1][a], dp[1][e], dp[1][i], dp[1][o], dp[1][u]
        a, e, i, o, u = 0, 1, 2, 3, 4  # 모음에 대한 인덱스 / Index for vowels
        mod = 10**9 + 7  # 큰 수 처리를 위해 모듈러 연산 사용 / Use modulo to handle large numbers.

        # 길이 2부터 n까지 dp 계산 / Calculate dp values from length 2 to n.
        for j in range(2, n + 1):
            # 길이 j에서 각 모음의 경우를 저장할 배열 초기화
            # Initialize an array to store possible counts for strings of length `j`.
            dp.append([0, 0, 0, 0, 0])
            # 'a'가 끝나는 경우는 이전 문자열이 'e', 'i', 'u'로 끝나야 함
            # 'a' can only follow 'e', 'i', or 'u'.
            dp[j][a] = (dp[j-1][e] + dp[j-1][i] + dp[j-1][u]) % mod
            # 'e'가 끝나는 경우는 이전 문자열이 'a', 'i'로 끝나야 함
            # 'e' can only follow 'a' or 'i'.
            dp[j][e] = (dp[j-1][a] + dp[j-1][i]) % mod
            # 'i'가 끝나는 경우는 이전 문자열이 'e', 'o'로 끝나야 함
            # 'i' can only follow 'e' or 'o'.
            dp[j][i] = (dp[j-1][e] + dp[j-1][o]) % mod
            # 'o'가 끝나는 경우는 이전 문자열이 'i'로 끝나야 함
            # 'o' can only follow 'i'.
            dp[j][o] = dp[j-1][i] % mod
            # 'u'가 끝나는 경우는 이전 문자열이 'i', 'o'로 끝나야 함
            # 'u' can only follow 'i' or 'o'.
            dp[j][u] = (dp[j-1][i] + dp[j-1][o]) % mod

        # 길이 n에서 가능한 모든 모음의 경우를 합산하여 결과 반환
        # Sum all possible counts for strings of length `n` and return the result.
        return sum(dp[n]) % mod