LeetCode 题解工作台
分隔长廊的方案数
在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 0 开始，长度为 n 的字符串 corridor ，它包含字母 'S' 和 'P' ，其中每个 'S' 表示一个座位，每个 'P' 表示一株植物。 在下标 0 的左边和下标 n - 1 的右边 已经 分别各放了一个屏风。你还需要额外…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\textit{dfs}(i, k)$，表示在走廊的第 个位置，已经放置了 个屏风的情况下，划分走廊的方案数。那么答案就是 $\textit{dfs}(0, 0)$。 函数 $\textit{dfs}(i, k)$ 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 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.length1 <= n <= 105corridor[i]要么是'S'，要么是'P'。
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示在走廊的第 个位置，已经放置了 个屏风的情况下，划分走廊的方案数。那么答案就是 。
函数 的计算过程如下：
如果 ，表示已经遍历完了走廊，此时如果 ，说明找到了一种划分走廊的方案，返回 ，否则返回 ；
否则，我们需要考虑当前位置 的情况：
- 如果 ，表示当前位置是一个座位，我们将 加 ；
- 如果 ，表示当前位置放置的屏风数量超过了 ，返回 ；
- 否则，我们可以选择不放置屏风，即 ；如果 ，我们还可以选择放置屏风，即 ；我们将这两种情况的结果相加并取模 ，即 。
最后，我们返回 。
时间复杂度 ，空间复杂度 。其中 是走廊的长度。
class Solution:
def numberOfWays(self, corridor: str) -> int:
@cache
def dfs(i: int, k: int) -> int:
if i >= len(corridor):
return int(k == 2)
k += int(corridor[i] == "S")
if k > 2:
return 0
ans = dfs(i + 1, k)
if k == 2:
ans = (ans + dfs(i + 1, 0)) % mod
return ans
mod = 10**9 + 7
ans = dfs(0, 0)
dfs.cache_clear()
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Are you correctly handling cases with fewer than two seats?
- question_mark
How do you efficiently count ways between consecutive two-seat segments?
- question_mark
Can you optimize space usage while maintaining state transition correctness?
常见陷阱
外企场景- error
Forgetting to check for odd number of seats, which makes division impossible.
- error
Counting sections without exactly two seats, violating problem constraints.
- error
Overcomplicating DP by storing full arrays instead of using minimal state transitions.
进阶变体
外企场景- arrow_right_alt
What if each section must contain exactly three seats instead of two?
- arrow_right_alt
Allow multiple dividers between positions and count the new number of ways.
- arrow_right_alt
Corridor contains additional obstacles that cannot be passed when dividing.