LC-2147 Hard LeetCode

2147. Number of Ways to Divide a Long Corridor

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 49% Topics: Math, String, Dynamic Programming

Reading material

Math & Geometry 12 min Strings 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

# greedy, combinatorics
class Solution(object):
    def numberOfWays(self, corridor):
        """
        :type corridor: str
        :rtype: int
        """
        MOD = 10**9+7
        result, cnt, j = 1, 0, -1
        for i, x in enumerate(corridor):
            if x != 'S':
                continue
            cnt += 1
            if cnt >= 3 and cnt%2:
                result = result*(i-j)%MOD
            j = i
        return result if cnt and cnt%2 == 0 else 0

Solution from kamyu104/LeetCode-Solutions · MIT