294. Flip Game II

문제: https://leetcode.com/problems/flip-game-ii/

Account Login - LeetCode

 

class Solution {
public:
    unordered_map<string, bool> cache;
    
    bool canWin(string currentState) {
        if(cache.find(currentState) != cache.end()){
            return cache[currentState];
        }
        bool &ret = cache[currentState];
        ret = true;
        
        for(int i = 0; i < currentState.size() - 1; i++){
            if(currentState[i] == '+' && currentState[i + 1] == '+'){
                currentState[i] = currentState[i + 1] = '-';
                ret &= canWin(currentState);
                currentState[i] = currentState[i + 1] = '+';
            }
        }
        return ret = !ret;
    }
};

 현재 "++"를 "--"로 바꿀 수 없다면 false를 리턴이다.  바꿀 수 있는 경우, 다음 턴으로 넘어가는데 다음 턴으로 가질 수 있는 모든 경우가 false이면 처음 시작하는 턴이 지는 것이므로 true를 반환해야한다.  이러한 game theory의 특성을 이용하여 return받는 값들을 모두 and로 취하고, ret가 false이면 반전시켜서 반환하도록 구현하였다.

 

 unordered_map을 써서 한 번 교체한 지점은 재방문하지 않도록 만들었다.

 

Time complexity: O(N)

Space complexity: O(N)