2147. 分隔長廊的方案數

思路

題目要求將一列字串切分，每段都剛好有兩個S的方法數。
只要將每段P中間的空隙數量相乘即為所求。

左到右遍歷，計算座位數量，在奇數時切分並更新答案。
（長度至少為 3，避免初始只有一張椅子的情況）

程式碼

動態規劃

class Solution {
public:
    int numberOfWays(string corridor) {
        const int MOD = 1e9 + 7;
        long long res = 1;
        int n = corridor.length();
        int seat = 0, lastSeatIndex = 0;
        for(int i = 0; i < n; ++i) {
            if(corridor[i] == 'S') {
                ++seat;
                if(seat >= 3 && seat % 2 == 1) {  
                    // 2, 3 一對, 4, 5 一對 ...
                    res = res * (i - lastSeatIndex) % MOD;
                }
                lastSeatIndex = i;
            }
        }
        // 總共的椅子數量若是奇數，那麼沒有辦法切分。
        if(seat == 0 || seat % 2 == 1) return 0;
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$