“This is the 11th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

I didn’t finish this problem in the competition, I saw the top guys on the list take four or five minutes to solve this problem, that’s the difference between me and the big guys. In fact, it was the middle of the night at that time, for me this kind of usually more than 10 o ‘clock to lie down to sleep, it is really some difficult, head dizzy, liver is not moving, and so on the second day have time to see their own topic also failed to make [embarrassment], see the big guy’s analysis just have ideas. This is the fourth question of the Biweekly Contest 70. It is difficult to understand the problem. It is actually to find a pattern.

describe

Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters ‘S’ and ‘P’ where each ‘S’ represents a seat and each ‘P’ represents a plant.

One room divider has already been installed to the left of index 0, and another to the right of index n – 1. Additional room dividers can be installed. For each position between indices i – 1 and i (1 <= i <= n – 1), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.

Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 10^9 + 7. If there is no way, return 0.

Example 1:

Input: corridor = "SSPPSPS"
Output: 3
Explanation: There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, each section has exactly two seats.
Copy the code

Note:

n == corridor.length
1 <= n <= 10^5
corridor[i] is either 'S' or 'P'.
Copy the code

parsing

The corridor has a row of seats and decorative plants. Corridor given a 0 index string of length N, consisting of the letters “S” and “P”, where each “S” represents a seat and each “P” represents a plant. As in example 1, a partition board has been installed to the left of index 0 and to the right of index N-1. In addition, at most one separator can be installed between each position between indexes i-1 and I (1 <= I <= n-1).

The question calls for dividing the corridor into sections, each with exactly two seats, allowing for any number of plants. It can be arranged in a number of ways. Returns the number of ways to divide a corridor. Since the answer is likely to be very large, it returns modulo 10^9 + 7. If nothing can be done, 0 is returned.

When I think about it, I think I have an idea to solve the problem. However, when I write the code, I find it more and more difficult, indicating that I still do not understand the topic deeply. Saw the big guy’s solution, is really penetrating, concise and easy to understand. We first initialize a list A that holds the index of corridor S. In fact, there are several ways to put partitions between the seat in position A [I] and the seat in position A [I +1], which is the value of a[I +1] -a [I]. Because we have set the scheme for the seat in position A [I] and the seat in position A [I +1], we need to move I backwards two places. To calculate the number of options for placing the partition between the next two seats, multiply the number of options each time, which is the final possible way to place the partition.

It should be noted that in corridor, when the number of S is odd or less than 2, partitions cannot be placed according to the meaning of the question, so 0 can only be returned directly. It’s going to be a big product for us, so we’re going to modulo 10 to the ninth plus 7.

answer

class Solution(object):
    def numberOfWays(self, corridor):
        """
        :type corridor: str
        :rtype: int
        """
        a = [i for i,c in enumerate(corridor) if c == 'S']
        res = 1
        for i in xrange(1, len(a) - 1, 2):
            res *= a[i+1] - a[i]
        return res % (10**9+7) * (len(a) % 2 == 0 and len(a) >= 2)  
Copy the code

The results

247/248 Test cases passed. Status: Accepted Runtime: 600 ms Memory Usage: 18.2 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation