LeetCode每日一题 - 2147. 分隔长廊的方案数

~~我都能写出来的也能算困难题吗~~

题面

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

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

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

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

思路

匹配到两个座位后计算第三个座位距离第二个座位的长度+1 即为中间可以放格挡的位置总数
各个总数相乘最终计算出所有可能性总数

代码

class Solution {
public:
    int numberOfWays(string corridor) {
        long long int y = 1000000007;
        if(corridor == "SS"){
            return 1;
        }
        if(corridor.length()==1){
            return 0;
        }
        int cnt=0;
        int cur=0;
        int last_cur=0;
        long long int ans=1;
        for(int i=0;i<corridor.length();i++){
            if(corridor[i] == 'S'){
                cnt++;
                last_cur=cur;
                cur=i;
            }
            if(cnt>=3){
                ans*=(i-last_cur);
                ans%=y;
                cnt=1;
            }
        }
        if(cnt%2==0 && cnt!=0){
            return ans;
        }else{
            return 0;
        }
    }
};