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 determine if the starting player can guarantee a win.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up:
Derive your algorithm‘s runtime complexity.
class Solution { public: bool canWin(string s) { if (s == "") return false; return canMove(s); } private: vector<string> generatePossibleNextMoves(string s) { vector<string> res; if(s.size()==0) return res; for(int i = 0;i<s.size()-1;i++) { if(s[i]==‘+‘ && s[i+1]==‘+‘) res.push_back(s.substr(0,i)+"--"+s.substr(i+2)); } return res; } bool canMove(string s) { vector<string> nextMoves = generatePossibleNextMoves(s); if(nextMoves.size()==0) return false; for(auto nextMove:nextMoves) { if(!canMove(nextMove)) return true; } return false; } };
原文：http://www.cnblogs.com/jxr041100/p/7885636.html