分隔长廊的方案数

难度: Hard

在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 0 开始，长度为 n 的字符串 corridor ，它包含字母 'S' 和 'P' ，其中每个 'S' 表示一个座位，每个 'P' 表示一株植物。

在下标 0 的左边和下标 n - 1 的右边已经分别各放了一个屏风。你还需要额外放置一些屏风。每一个位置 i - 1 和 i 之间（1 <= i <= n - 1），至多能放一个屏风。

请你将走廊用屏风划分为若干段，且每一段内都 恰好有两个座位 ，而每一段内植物的数目没有要求。可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为不同方案。

请你返回划分走廊的方案数。由于答案可能很大，请你返回它对 10⁹ + 7 取余的结果。如果没有任何方案，请返回 0 。

示例 1：

输入：corridor = "SSPPSPS"
输出：3
解释：总共有 3 种不同分隔走廊的方案。
上图中黑色的竖线表示已经放置好的屏风。
上图每种方案中，每一段都恰好有 两个 座位。

示例 2：

输入：corridor = "PPSPSP"
输出：1
解释：只有 1 种分隔走廊的方案，就是不放置任何屏风。
放置任何的屏风都会导致有一段无法恰好有 2 个座位。

示例 3：

输入：corridor = "S"
输出：0
解释：没有任何方案，因为总是有一段无法恰好有 2 个座位。

提示：

n == corridor.length
1 <= n <= 10⁵
corridor[i] 要么是 'S' ，要么是 'P' 。

Submission

运行时间: 203 ms

内存: 16.5 MB

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        ret = 1
        p_cnt = 0
        s_cnt = 0
        for item in corridor:
            if item == 'P':
                if s_cnt == 2:
                    p_cnt += 1
                continue

            if s_cnt != 2:
                s_cnt += 1
                continue
            
            ret = ret * (p_cnt + 1) % (10**9 + 7)
            p_cnt = 0
            s_cnt = 1
        return ret if s_cnt == 2 else 0

Explain

该题解采用了遍历字符串的方法来数座位'S'，当数到两个座位时，计算从这两个座位之后到下一对两个座位之前的植物'P'的个数。这些植物的数量加1（自身位置）就是放置屏风的方案数。这样，每到达一个新的两座位的组合，就用之前计算的方案数去乘以当前的方案数（即植物数加1），并取模以防止数字过大。最后，如果整个走廊中最后的座位计数为2，则返回计算的结果，否则返回0，因为无法完成任务。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        ret = 1  # 初始化方案数为1
        p_cnt = 0  # 植物计数器
        s_cnt = 0  # 座位计数器
        for item in corridor:
            if item == 'P':
                if s_cnt == 2:  # 当已有两个座位时，计数植物
                    p_cnt += 1
                continue

            if s_cnt != 2:  # 当座位不足两个时，继续计数座位
                s_cnt += 1
                continue
            
            ret = ret * (p_cnt + 1) % (10**9 + 7)  # 计算新的方案数
            p_cnt = 0  # 重置植物计数器
            s_cnt = 1  # 开始新的座位计数
        return ret if s_cnt == 2 else 0  # 如果最后恰好有两个座位，返回结果，否则返回0

Explore

在算法中，如果最后的座位计数不是2，返回0的原因在于无法形成有效的屏风放置方案。根据题目要求，每两个座位之间至少需要一面屏风，如果最后的座位计数不是2，则说明最后一组座位之后没有更多的座位来形成新的对，从而无法满足每两个座位之间至少有一个屏风的条件。因此，如果座位没有恰好配对完毕（即总数为偶数且完全成对），则无法完成任务，返回0。

是的，算法中每遇到两个座位就重置植物计数器，意味着只计算这两个座位之间的植物数。这是因为每两个座位之间的屏风放置方案数量取决于它们之间的植物数。多余的植物，即在最后一对座位之后的植物，在该算法中不被计入任何屏风放置方案，因为它们不位于任何两个座位之间，无法用于形成新的配对或屏风放置方案。

这一步骤通过乘法原理确保考虑了所有可能的屏风放置方式。对于每一对座位，其间的植物数(p_cnt)加1（包括零个植物的情况）表示这对座位之间可以放置屏风的方案数。通过将每一对座位的方案数相乘，算法累积了所有可能的屏风放置组合。取模操作是为了处理大数问题，确保结果不会因数值过大而错误。

如果字符串`corridor`以多个植物'P'结尾，这些植物在算法中不被考虑，因为它们不位于任何两个座位之间。这意味着这些植物不影响最终的方案数，因为方案数只与座位之间的植物有关。因此，结尾的植物不会增加也不会减少屏风放置的方案数。