Leetcode Problem 2147. Number of Ways to Divide a Long Corridor

2147. Number of Ways to Divide a Long Corridor

Leetcode Solutions

Combinatorics, Space Optimized

  1. Initialize MOD to 1000000007 for modulo operations.
  2. Initialize count to 1, previous_pair_last to null, and seats to 0.
  3. Iterate over the corridor string.
    • If the current character is 'S', increment seats.
    • If seats equals 2, update previous_pair_last to the current index and reset seats to 0.
    • If seats equals 1 and previous_pair_last is not null, multiply count by the difference between the current index and previous_pair_last, then take modulo MOD.
  4. If seats equals 1 after iteration, return 0 (odd number of seats).
  5. If previous_pair_last is null, return 0 (no seats).
  6. Return count.
UML Thumbnail

Top-Down Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...