1059. Plus-Plus Flip Game
A light-up panel is a row of lamps described by the string state: '+' is a lit lamp and '-' is a dark one. Two players alternate turns, and on a turn the mover must pick two neighbouring lit lamps and switch both off, turning "++" into "--".
A player who has no pair of adjacent lit lamps on their turn loses. The first player moves first and both play perfectly. Return true if the first player can force a win from state, otherwise false. Trying every sequence of moves is exponential; aim for roughly quadratic time in the longest block of lit lamps by exploiting that separate blocks do not interact.
Example 1
- Input:
- state = "+-+++"
- Output:
- true
- Explanation:
The first player darkens the first two lamps of the run of three, leaving one lit lamp, so the opponent has no pair to flip and loses.
Example 2
- Input:
- state = "+-+-++-"
- Output:
- true
- Explanation:
Only one adjacent lit pair exists; the first player darkens it and the opponent has no move, so the first player wins.
Example 3
- Input:
- state = "++-++"
- Output:
- false
- Explanation:
Whichever pair the first player darkens, the second player darkens the other pair and the first player is stuck.
Constraints
1 ≤ state.length ≤ 4000
state contains only the characters '+' and '-'
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(m^2), m = longest run of '+'
- Space
- O(n)