LeetCode 筆記 - 1641. Count Sorted Vowel Strings

題目在此 1641. Count Sorted Vowel Strings

給一個整數 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)

也許你也會想看看

• LeetCode 筆記 - 1759. Count Number of Homogenous Substrings
• LeetCode 筆記 - 2785. Sort Vowels in a String
• LeetCode 筆記 - 567. Permutation in String