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
}