Thursday, October 15, 2015

LeetCode [293] Flip Game

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 [].
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        int n = s.size();
        vector<string> ret;
        for(int i=0; i<n-1; ++i){
            if(s.substr(i,2)=="++"){
                string tmp = s; 
                tmp[i] = '-';
                tmp[i+1] = '-';
                ret.push_back(tmp);
            }
        }
        return ret;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
//Java
class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        int n = s.length();
        List<String> ret = new ArrayList<>();
        for(int i=0; i<n-1; ++i){
            StringBuilder sb = new StringBuilder(s);
            if(sb.substring(i, i+2).equals("++")){
                sb.replace(i, i+2, "--");
                ret.add(sb.toString());
            }
        }
        return ret;
    }
}

No comments:

Post a Comment