Skip to main content

1641. Count Sorted Vowel Strings

https://leetcode.com/problems/count-sorted-vowel-strings/

Python​

Use itertools from python​

可重複組合，在python itertools中有combinations_with_replacement可以用

from itertools import combinations_with_replacement

class Solution:
    def countVowelStrings(self, n: int) -> int:
        cmbs = [0 for cmb in combinations_with_replacement('aeiou', n)]

        return len(cmbs)

Top-Down DP​

from functools import cache


class Solution:
    def countVowelStrings(self, n: int) -> int:
        @cache
        def count(n,vow):
            if vow == 0:
                return 0
            if n == 0:
                return 1
            return count(n,vow-1) + count(n-1,vow)

        return count(n,5)

Bottom-Up DP​

from collections import defaultdict

class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = defaultdict(dict)

        for vowel in range(1, 6):
            dp[1][vowel] = vowel

        for value in range(2, n+1):
            dp[value][1] = 1
            for vowel in range(2, 6):
                dp[value][vowel] = dp[value][vowel-1] + dp[value-1][vowel]

        return dp[n][5]