LeetCode 筆記 - 1641. Count Sorted Vowel Strings

題目在此 1641. Count Sorted Vowel Strings

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

解題思維

這題其實等價成 Xa + Xe + Xi + Xo + Xu = n,而 X 皆屬於非負整數解
5 個格子所以有 4 個隔板

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

所以公式就會長這樣

image 22

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)

也許你也會想看看