Flip Game Python Solution with Tests

LeetCode 293, Easy. Topics: String. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 14 parametrized pytest cases, and a playground notebook:

lcpy gen -n 293   # by problem number
lcpy gen -s flip_game   # by problem name

Problem

You are playing a Flip Game with your friend. You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner. Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].

Examples

Input: currentState = "++++"
Output: ["--++","+--+","++--"]

Input: currentState = "+"
Output: []

Constraints

1 <= currentState.length <= 500
currentState[i] is either '+' or '-'.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n^2) where n is the string length
    # Space: O(n) excluding the output
    def generate_possible_next_moves(self, current_state: str) -> list[str]:
        results: list[str] = []
        for i in range(len(current_state) - 1):
            if current_state[i : i + 2] == "++":
                results.append(current_state[:i] + "--" + current_state[i + 2 :])
        return results

Complexity

Time	Space
O(n^2) where n is the string length	O(n) excluding the output

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Flip Game Python Solution with Tests

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags