leetcode 2147. 分隔长廊的方案数 困难

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

分析：由于题目已经限定了，划分出来的每一段必须要有两个座位。可以遍历整个字符串，当出现过两个 'S' 之后，再统计之后出现过多少个 'P'，只有在出现过两个座位后，出现的植物之间才可以放置屏风。这里连续出现的 'P' 的个数，就是这一段可以放置的屏风数量。之后一直这样统计，直到末尾，把每一段屏风数量相乘，就能得到答案。

注意如果座位的数量是奇数，则无法放置任何屏风。

int numberOfWays(char* corridor) { long long ans=1,mod=1e9+7; int cnt_s=0,cnt_p=0,cnt=0; int num[100010]={0}; for(int i=0;corridor[i];++i) { if(cnt_s==2) { if(corridor[i]=='S')num[cnt++]=cnt_p+1,cnt_p=0,cnt_s=1; else if(corridor[i]=='P')cnt_p+=1; } else if(corridor[i]=='S')cnt_s++; } if(cnt==0) { if(cnt_s==2)return 1; else return 0; } else { if(cnt_s==1)return 0; else for(int i=0;i<cnt;++i) ans=ans*num[i]%mod; } return ans; }