[leetcode] 294. Flip Game II解題レポート
タイトルリンク:https://leetcode.com/problems/flip-game-ii/
You are playing the following Flip Game with your friend: Given a string that contains only these two characters:
Write a function to determine if the starting player can guarantee a win.
For example, given
Follow up: Derive your algorithm's runtime complexity.
考え方:それぞれの状況を列挙して、それから次の階に戻って、相手が勝つことができるかどうかを見て、相手が勝つことがある場合、必ず勝つことができることを保証することはできません.時間の複雑さは指数です.
O(n)は時間内に解決できますが、ちょっと面倒なので、この解の面接は普通十分です.興味があればまた探してみましょう.
コードは次のとおりです.
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.
考え方:それぞれの状況を列挙して、それから次の階に戻って、相手が勝つことができるかどうかを見て、相手が勝つことがある場合、必ず勝つことができることを保証することはできません.時間の複雑さは指数です.
O(n)は時間内に解決できますが、ちょっと面倒なので、この解の面接は普通十分です.興味があればまた探してみましょう.
コードは次のとおりです.
class Solution {
public:
bool canWin(string s) {
int len = s.size();
vector<string> strs;
for(int i = 0; i< len-1; i++)
if(s[i] == '+' && s[i+1] == '+')
strs.push_back(s.substr(0, i)+"--"+s.substr(i+2));
for(auto str: strs)
if(!canWin(str))
return true;
return false;
}
};