-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
34 lines (33 loc) · 877 Bytes
/
Solution.cs
File metadata and controls
34 lines (33 loc) · 877 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution
{
public int NumberOfWays(string corridor)
{
// remove prev and tail 'P'
corridor = corridor.Trim('P');
if (corridor.Length < 2) return 0;
return (int)DP(0, corridor);
}
int mod = (int)1e9 + 7;
Dictionary<int, long> memo = [];
long DP(int pos, string corridor)
{
int n = corridor.Length;
if (pos >= n) return 1;
if (memo.TryGetValue(pos, out long value)) return value;
int i = pos;
int count = 0;
while (i < n && count < 2)
{
count += corridor[i] == 'S' ? 1 : 0;
i++;
}
if (count < 2) return memo[pos] = 0;
int can = 1;
while (i < n && corridor[i] == 'P')
{
can++;
i++;
}
return memo[pos] = 1L * can * DP(i, corridor) % mod; ;
}
}