LC-0903 Hard LeetCode

903. Valid Permutations for DI Sequence

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 57% Topics: String, Dynamic Programming, Prefix Sum

Reading material

Strings 12 min 1-D Dynamic Programming 16 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(n)

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

Solution from kamyu104/LeetCode-Solutions · MIT