※ 引述《Neuenmuller (苏菲・诺伊恩谬拉)》之铭言：
: Code 2(参考了Leetcode上solution里Lee大师的做法):
: class Solution {
: public:
: int numberOfWays(string corridor) {
: long output = 1, count = 0;
: for (int i = 0, j = 0; i < corridor.size(); i++) {
: if (corridor[i] == 'S') {
: count++;
: if (count > 2 && count % 2 == 1) {
: output *= (i - j);
: output %= 1'000'000'007;
: }
: j = i;
: }
: }
: if (!count || count % 2 != 0) return 0;
: return output;
: }
: };
: 用count % 2来数有几组椅子，count不归零
: 第一个是用这个来找一组椅子跟下一组椅子比较简单
: 第二个是如果遇到没有椅子或是只有奇数个椅子的edge case都可以用count解决
: 另外我原本解里面的头尾问题也不用解决
: 这就是大师跟我的差距 :(
lee 的另一个做法我也很喜欢 DP状态转移
a, b, c 分别代表目前圈到的区域有0, 1, 2个座位的情况下
方法数有多少
如果遇到座位
0 个座位的情况会变成 1 个座位
1 个座位的情况就变成 2 个座位
2 个座位等于这个区域要强制结束开始画新区域 而新区域由新座位开始所以也是 1
所以遇到座位时 a, b, c = 0, a+c, b
遇到盆栽的情况就可以考虑要不要画新区域了
0 或 1 个座位的情况不行 因为还没圈到 2 个座位
2 个座位的情况就可以选择要把盆栽圈到目前的区域 或是开始一个新区域
而这个新区域就只有一个盆栽 所以是 0 个座位
也就是 a, b, c = a+c, b, c
最后的话就是看那些合法的状态 也就是目前的区域要有 2 个座位( 0 个不行)
所以直接回传 c 就好
Python code:
class Solution:
def numberOfWays(self, corridor: str) -> int:
mod = 10**9+7
a, b, c = 1, 0, 0
for ch in corridor:
if ch == 'S':
a, b, c = 0, a+c, b
else:
a += c
return c % mod