2147. Number of Ways to Divide a Long Corridor
你在一个图书馆走廊
开头跟尾端已经各放好一个屏风
走廊上有很多椅子S跟中型盆栽P排成一列
你要在中间补上屏风
每个屏风中间要刚好有两个椅子以及不限数量的盆栽
回传一共有几种放法(mod 10^9+7)
Input: corridor = "SSPPSPS" Output: 3
|SS|PPSPS|
|SSP|PSPS|
|SSPP|SPS|
Input: corridor = "PPSPSP" Output: 1
|PPSPSP|
Input: corridor = "S" Output: 0
Intuition:
分成椅子已填满跟未填满两种状态
然后计算可能性乘上去
Approach:
本来要写FSM
可是后来发现只有两个状态就懒了
直接用一个bool切换状态
计算的时候会分成已填满跟未填满两个状态
未填满的话遇到盆栽不做事
遇到座位计数+1
椅子已填满的话就计算有几个盆栽就会多几种摆的可能
然后遇到座位就回到未填满
未填满跟填满的时候count是不同意义
不过我懒得多用一个变量就直接塞进去了
如果是在专案内的话我会分两个变量用提升可读性
TS Code:
const mod = 1000000007
function numberOfWays (corridor: string): number {
let result = 1
let count = 0
let isFill = false
const unfilled = (cur: string): void => {
if (cur === 'S') {
if (count === 1) {
isFill = true
return
}
count++
}
}
const filled = (cur: string): void => {
switch (cur) {
case 'S':
result = (result * count) % mod
isFill = false
count = 1
return
case 'P':
count++
return
}
}
for (let i = 0; i < corridor.length; i++) {
isFill ? filled(corridor[i]) : unfilled(corridor[i])
}
if (!isFill && count < 2) return 0
return result
}