Участник:Easik/valid-permutations-for-di-sequence

Материал из DISCOPAL
Перейти к: навигация, поиск

Python

class Solution(object):
    def numPermsDISequence(self, S):
        """
        :type S: str
        :rtype: int
        """
 
        # Array to store heuristic's temporal results
        dp = (len(S) + 1) * [1]
 
        for char in S:
 
            # Increasing character - pop end item & sum pairs in right direction
            if char == "I":
 
                dp = dp[:-1]
                for i in range(1, len(dp)):
                    dp[i] += dp[i - 1]
 
            # Decreasing character - pop front item & sum pairs in left direction
            else:
 
                dp = dp[1:]
                for i in range(len(dp) - 1 - 1, 0 - 1, -1):
                    dp[i] += dp[i + 1]
 
        # After all list reduces left with a single item with v/ of possible permutations
        return dp[0] % (10 ** 9 + 7)