LeetCode-Python-294。フリップIIゲーム

Leetcode Python 294 Flip Ii Game

あなたとあなたの友達は、ゲームの「フリップゲーム」ゲームルールと呼ばれるプレイをします。+と-の文字列のみが与えられます。あなたとあなたの友達は交代で2つの連続した「++」を「-」に戻します。一方のパーティが効果的に反転できない場合、ゲームの終了を意味し、もう一方のパーティが勝ちます。

ソリューションを勝ち取った最初のプレーヤーが存在するかどうかを判断する関数を記述してください。

例：

入力：s = '++++'
出力：true
分析：最初のプレーヤーは「++」の途中で「+」に反転し、勝つ可能性があります。
拡張：
アルゴリズムの時間計算量を導き出します。

出典：滞在ボタン（LeetCode）
リンク：https：//leetcode-cn.com/problems/flip-game-ii
すべての著作権カラーボタンをネットワーク化します。商業的復刻は公認の公式に連絡してください、非営利的復刻は出典を示してください。

最初のアイデア：

一度ひっくり返した後、負ける新しいストリングフレンドを生成し、私に代わって勝った場合、

友達が負けると判断する方法は負けないのですか？それ自体への再帰呼び出し。

class Solution(object): def canWin(self, s): ''' :type s: str :rtype: bool ''' for i in range(len(s) - 1): if s[i:i + 2] == '++' and not self.canWin(s[:i] + '--' + s[i + 2:]): return True return False

2番目のアイデア：

最初のアイデアは比較的遅く、印刷は各呼び出しで見つけることができ、繰り返されます、

そのため、今回は、ハッシュテーブルを使用して各呼び出しの応答を格納し、メソッドの記憶を取りたいと思うかもしれません。

class Solution(object): def canWin(self, string): ''' :type s: str :rtype: bool ''' record = {} def helper(s): if s in record: return record[s] for i in range(len(s) - 1): if s[i:i + 2] == '++': next_s = s[:i] + '--' + s[i + 2:] if not helper(next_s): record[next_s] = False return True return False return helper(string)