2147. Number of Ways to Divide a Long Corridor

Обновлено: 2024-03-12
1 мин
[]

Содержание

LeetCode problem 2147

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        @cache
        def dfs(i, cnt):
            if i == n:
                return int(cnt == 2)
            cnt += corridor[i] == 'S'
            if cnt > 2:
                return 0
            res = dfs(i + 1, cnt)
            if cnt == 2:
                res += dfs(i + 1, 0)
                res %= mod
            return res

        n = len(corridor)
        mod = 10**9 + 7
        res = dfs(0, 0)
        dfs.cache_clear()
        return res