Welcome to Subscribe On Youtube

293. Flip Game

Description

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 [].

 

Example 1:

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

Example 2:

Input: currentState = "+"
Output: []

 

Constraints:

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

Solutions

Start traversing from the second letter, each time it is judged whether the current letter is +, and the previous letter is +, if both are plus, the reversed string will be stored in the result.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public List<String> generatePossibleNextMoves(String currentState) {
          char[] cs = currentState.toCharArray();
          List<String> ans = new ArrayList<>();
          for (int i = 0; i < cs.length - 1; ++i) {
              if (cs[i] == '+' && cs[i + 1] == '+') {
                  cs[i] = '-';
                  cs[i + 1] = '-';
                  ans.add(String.valueOf(cs));
                  cs[i] = '+';
                  cs[i + 1] = '+';
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      vector<string> generatePossibleNextMoves(string currentState) {
          vector<string> ans;
          for (int i = 0; i < currentState.size() - 1; ++i) {
              if (currentState[i] == '+' && currentState[i + 1] == '+') {
                  currentState[i] = '-';
                  currentState[i + 1] = '-';
                  ans.push_back(currentState);
                  currentState[i] = '+';
                  currentState[i + 1] = '+';
              }
          }
          return ans;
      }
  };
  

• '''
  
  >>> a="abc"
  >>> a[1:99]
  'bc'
  >>> a[:0]
  ''
  
  '''
  class Solution(object):
    def generatePossibleNextMoves(self, s):
      """
      :type s: str
      :rtype: List[str]
      """
      ans = []
      for i in range(0, len(s) - 1):
        if s[i:i + 2] == "++":
          ans.append(s[:i] + "--" + s[i + 2:])
      return ans
  
  ############
  
  class Solution:
      def generatePossibleNextMoves(self, currentState: str) -> List[str]:
          s = list(currentState)
          ans = []
          for i, c in enumerate(s[:-1]):
              if c == "+" and s[i + 1] == "+":
                  s[i] = s[i + 1] = "-"
                  ans.append("".join(s))
                  s[i] = s[i + 1] = "+"
          return ans
  
  

• func generatePossibleNextMoves(currentState string) []string {
  	ans := []string{}
  	cs := []byte(currentState)
  	for i, c := range cs[1:] {
  		if c == '+' && cs[i] == '+' {
  			cs[i], cs[i+1] = '-', '-'
  			ans = append(ans, string(cs))
  			cs[i], cs[i+1] = '+', '+'
  		}
  	}
  	return ans
  }
  

• function generatePossibleNextMoves(currentState: string): string[] {
      const s = currentState.split('');
      const ans: string[] = [];
      for (let i = 0; i < s.length - 1; ++i) {
          if (s[i] === '+' && s[i + 1] === '+') {
              s[i] = s[i + 1] = '-';
              ans.push(s.join(''));
              s[i] = s[i + 1] = '+';
          }
      }
      return ans;
  }
  
  

All Problems

All Solutions