LC 1220

Solution to LeetCode 1220 Count Vowels Permutation.

LeetCode 1220

Count Vowels Permutation (Hard). [link]

1. Dynamic Programming. According to the problem statement, the rule can be written as

   • ‘e’, ‘i’, ‘u’ can be in front of ‘a’.

   • ‘a’, ‘i’ can be in front of ‘e’.

   • ‘e’, ‘o’ can be in front of ‘i’.

   • ‘i’ can be in front of ‘o’.

   • ‘o’,’i’ can be behind ‘u’.

   According to the above rule, the number of strings of length N can be represent in DP function:

   • dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4]

   • dp[i][1] = dp[i-1][0] + dp[i-1][2]

   • dp[i][2] = dp[i-1][1] + dp[i-1][3]

   • dp[i][3] = dp[i-1][2]

   • dp[i][4] = dp[i-1][2] + dp[i-1][3]

   where 0-4 represents ‘a’, ‘e’, ‘i’, ‘o’, ‘u’. The length N can be calculated as the sum of the above five dp.

   The time complexity is O(CN). The space complexity is O(C). (C = 5. N = n)

class Solution(object):
    def countVowelPermutation(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = (1,1,1,1,1)
        modulo = 1000000007
        for _ in range(n-1):
            rule1 = (dp[1] + dp[2] + dp[4]) % modulo
            rule2 = (dp[0] + dp[2]) % modulo
            rule3 = (dp[1] + dp[3]) % modulo
            rule4 = dp[2]
            rule5 = (dp[2] + dp[3]) % modulo
            dp = (rule1, rule2, rule3, rule4, rule5)
        return sum(dp) % modulo

2. Matrix Power.

   Time complexity O(C^3 log N). Matrix multiplication takes O(N^3) and there are at most log N times of matrix multiplications. Space complexity O(C^2). (C = 5)

import numpy as np
class Solution(object):
    def countVowelPermutation(self, n):
        """
        :type n: int
        :rtype: int
        """
        matrix = np.mat([
            (0,1,0,0,0),
            (1,0,1,0,0),
            (1,1,0,1,1),
            (0,0,1,0,1),
            (1,0,0,0,0)
        ], np.dtype('O'))
        
        res = np.mat([(1,1,1,1,1)], np.dtype('O'))
        modulo = 1000000007
        n -= 1
        while n > 0:
            if n % 2 == 1:
                res = res * matrix
            matrix = (matrix ** 2) % modulo
            n //= 2
        return res.sum() % modulo