algorithm notes: leetcode#293 flip game

Problem

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + 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.

Write a function to compute all possible states of the string after one valid move.

Example:

Input: s = “++++“
Output:
[
”--++”,
"+--+",
"++--"
]
Note: If there is no valid move, return an empty list [].

Solution

Analysis

Iterate from the second character to the last character and check whether s[i-1:i+1] == "++", if so, replace "++" with "--" and put it into the list to return.

Python implementation

1
2
3
4
5
6
7

class :
    def generatePossibleNextMoves(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        return [s[:i-1]+"--"+s[i+1:] for i in range(1, len(s)) if s[i-1:i+1]=="++"]

Java implementation

1
2
3
4
5
6
7
8
9
10
11
12

class  {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> ans = new ArrayList<>();
        
        for(int i = 1; i < s.length(); i++){
            if(s.substring(i-1, i+1).equals("++")){
                ans.add(s.substring(0,i-1)+"--"+s.substring(i+1));
            }
        }
        return ans;
    }
}

Time complexity

O(N).

Space complexity

O(N).

Links

293. Flip Game
(中文版)