903.md

903 Valid Permutations for DI Sequence

Description

link

---

Solution

see solution

---

Code

Complexity T : O(N^2) M : O(N)

class Solution:
    def numPermsDISequence(self, S):
        """
        :type S: str
        :rtype: int
        """
        dp = [1 for _ in range(len(S) + 1)]
        
        for c in S:
            if c == 'I':
                dp = dp[:-1]
                for i in range(1, len(dp)):
                    dp[i] += dp[i - 1]
            else:
                dp = dp[1:]
                for i in range(len(dp) - 2, -1, -1):
                    dp[i] += dp[i + 1]
        
        return dp[0] % (10 ** 9 + 7)