1220. Count Vowels Permutation

Hard

Description

給定一個整數 n，計算長度為 n 的字串中，由母音字母 (a, e, i, o, u) 組成且符合以下規則的字串數量（結果對 10^9+7 取餘）：
a 後面只能接 e
e 後面只能接 a 或 i
i 後面不能接 i
o 後面只能接 i 或 u
u 後面只能接 a

Example:

Input: n = 2 Output: 10

Intuition#

狀態轉移 DP：根據每個母音的後繼規則，逐步累加長度為 n 的合法排列數。

以每個母音結尾的字串數量為狀態
根據規則反向推導：哪些母音可以接在某母音之前
a 可以被 e, i, u 接在前面；e 可以被 a, i 接在前面…

Approaches#

1: 2D DP#

概念: dp[i][v] 表示長度為 i、以母音 v 結尾的字串數。根據轉移規則從 dp[i-1] 推導。
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun countVowelPermutation(n: Int): Int {
        val MOD = 1_000_000_007L
        val dp = Array(n) { LongArray(5) }
        // 0=a, 1=e, 2=i, 3=o, 4=u
        for (j in 0..4) dp[0][j] = 1

        for (i in 1 until 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
        }
        return (dp[n - 1].sum() % MOD).toInt()
    }
}

⭐2: 空間優化 DP#

概念: 只需要五個變數記錄上一輪各母音的數量。
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun countVowelPermutation(n: Int): Int {
        val MOD = 1_000_000_007L
        var a = 1L; var e = 1L; var i = 1L; var o = 1L; var u = 1L

        repeat(n - 1) {
            val na = (e + i + u) % MOD
            val ne = (a + i) % MOD
            val ni = (e + o) % MOD
            val no = i % MOD
            val nu = (i + o) % MOD
            a = na; e = ne; i = ni; o = no; u = nu
        }
        return ((a + e + i + o + u) % MOD).toInt()
    }
}

🔑 Takeaways#

Pattern: 狀態機 DP — 每個狀態（母音）有固定的轉移規則
關鍵技巧: 反向思考轉移關係（誰可以轉移到當前狀態）比正向更直觀；常數個狀態可以壓縮至 O(1) 空間