Hard

题目描述

沿着一条长长的图书馆走廊，有一排座椅和装饰植物。给你一个长度为 n 的下标从 0 开始的字符串 corridor，其中 corridor[i] 要么是字母 ‘S’，要么是字母 ‘P’。‘S’ 表示座椅，‘P’ 表示植物。

在下标 0 的左侧和下标 n - 1 的右侧已经分别各有一个房间隔板。现在还可以额外安装房间隔板。对于每个位置，在下标 i - 1 和 i 之间（1 <= i <= n - 1），最多能安装一个隔板。

要将走廊分割成若干段，每一段恰好包含两个座椅，可以有任意数量的植物。可能有多种方式来执行分割。如果有一个位置在第一种分割方式中安装了隔板，而在第二种分割方式中没有安装隔板，那么这两种分割方式就是不同的。

返回分割走廊的方案数。由于答案可能很大，请返回对 10^9 + 7 取余的结果。如果不存在分割方案，则返回 0。

示例 1:

输入：corridor = "SSPPSPS"
输出：3
解释：总共有 3 种不同的分割走廊的方法。
注意，在每种方法中，每个部分都恰好有两个座椅。

示例 2:

输入：corridor = "PPSPSP"
输出：1
解释：只有 1 种分割走廊的方法，就是不安装任何额外的隔板。
安装任何隔板都会创建一个不恰好包含两个座椅的部分。

示例 3:

输入：corridor = "S"
输出：0
解释：无法分割走廊，因为总是会有一个部分不恰好包含两个座椅。

提示：

  • n == corridor.length
  • 1 <= n <= 10^5
  • corridor[i] 是 ‘S’ 或 ‘P’

解题思路

这是一道需要仔细分析的动态规划/数学题。

首先，我们需要理解题目要求：每个分段必须恰好包含2个座椅，可以包含任意数量的植物。这意味着总座椅数必须是偶数，否则无法分割。

解题思路：

  1. 预处理：统计所有座椅的位置。如果座椅总数不是偶数或为0，直接返回0。

  2. 分段分析：每两个座椅形成一个段，我们需要在相邻段之间放置隔板。关键观察是：相邻两段之间必须恰好放置一个隔板。

  3. 计算方案数：假设第i段的最后一个座椅位置是pos1，第i+1段的第一个座椅位置是pos2，那么隔板可以放在pos1+1到pos2之间的任意位置，共有pos2-pos1种选择。

  4. 乘法原理：所有相邻段之间的选择方案数相乘，就是最终答案。

算法步骤：

  • 找出所有座椅位置
  • 检查座椅数量是否为偶数且大于0
  • 计算相邻段之间可放置隔板的位置数
  • 将所有位置数相乘得到最终结果

时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    int numberOfWays(string corridor) {
        const int MOD = 1000000007;
        vector<int> seats;
        
        // 找出所有座椅位置
        for (int i = 0; i < corridor.length(); i++) {
            if (corridor[i] == 'S') {
                seats.push_back(i);
            }
        }
        
        // 座椅数必须是偶数且大于0
        if (seats.size() == 0 || seats.size() % 2 == 1) {
            return 0;
        }
        
        long long result = 1;
        
        // 计算相邻段之间可放置隔板的方案数
        for (int i = 1; i < seats.size() / 2; i++) {
            int endOfPrevSection = seats[2 * i - 1];  // 前一段的最后一个座椅
            int startOfCurrSection = seats[2 * i];    // 当前段的第一个座椅
            
            // 隔板可以放在这两个位置之间的任意位置
            int ways = startOfCurrSection - endOfPrevSection;
            result = (result * ways) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 1000000007
        
        # 找出所有座椅位置
        seats = []
        for i, c in enumerate(corridor):
            if c == 'S':
                seats.append(i)
        
        # 座椅数必须是偶数且大于0
        if len(seats) == 0 or len(seats) % 2 == 1:
            return 0
        
        result = 1
        
        # 计算相邻段之间可放置隔板的方案数
        for i in range(1, len(seats) // 2):
            end_of_prev_section = seats[2 * i - 1]  # 前一段的最后一个座椅
            start_of_curr_section = seats[2 * i]    # 当前段的第一个座椅
            
            # 隔板可以放在这两个位置之间的任意位置
            ways = start_of_curr_section - end_of_prev_section
            result = (result * ways) % MOD
        
        return result

public class Solution {
    public int NumberOfWays(string corridor) {
        const int MOD = 1000000007;
        var seats = new List<int>();
        
        // 找出所有座椅位置
        for (int i = 0; i < corridor.Length; i++) {
            if (corridor[i] == 'S') {
                seats.Add(i);
            }
        }
        
        // 座椅数必须是偶数且大于0
        if (seats.Count == 0 || seats.Count % 2 == 1) {
            return 0;
        }
        
        long result = 1;
        
        // 计算相邻段之间可放置隔板的方案数
        for (int i = 1; i < seats.Count / 2; i++) {
            int endOfPrevSection = seats[2 * i - 1];  // 前一段的最后一个座椅
            int startOfCurrSection = seats[2 * i];    // 当前段的第一个座椅
            
            // 隔板可以放在这两个位置之间的任意位置
            int ways = startOfCurrSection - endOfPrevSection;
            result = (result * ways) % MOD;
        }
        
        return (int)result;
    }
}

var numberOfWays = function(corridor) {
    const MOD = 1000000007;
    const seats = [];
    
    // 找出所有座椅位置
    for (let i = 0; i < corridor.length; i++) {
        if (corridor[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串长度。需要遍历一次字符串找出座椅位置，然后遍历座椅数组计算方案数
空间复杂度O(k)，其中 k 是座椅数量。需要存储所有座椅的位置

相关题目