LeetCode 筆記 - Count Sorted Vowel Strings

計算長度為 n 且按字典序排列的母音組合數量。作者跳出傳統遞迴，運用高中數學的「隔板法」將問題轉化為組合公式。透過 O(1) 的數學運算直接求出解答，展示了數學建模在解決計算問題時的極致效率。

發佈

2022.05.11

閱讀

約 1 分鐘

字數

197

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

給一個整數 n ，計算出有幾種長度為 n 的按照字典順序排列的 a, e, i, o, u 排列組合

解題思維

這題其實等價成 X_a + X_e + X_i + X_o + X_u = n，而 X 皆屬於非負整數解
5 個格子所以有 4 個隔板

相關數學可以參考 Wiki 隔板法

所以公式就會長這樣

Time complexity: O(1)

1
2
3

class Solution:
    def countVowelStrings(self, n: int) -> int:
        return int((n + 4) * (n + 3) * (n + 2) * (n + 1) / 24)