# Time:  O(c * n * c!), n is length of string, c is count of "++"
# Space: O(c * n), recursion would be called at most c in depth.
#                  Besides, it costs n space for modifying string at each depth.

class Solution(object):
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        i, n = 0, len(s) - 1
        is_win = False
        while not is_win and i < n:                                     # O(n) time
            if s[i] == '+':
                while not is_win and i < n and s[i+1] == '+':           # O(c) time
                     # t(n, c) = c * (t(n, c-1) + n) + n = ...
                     # = c! * t(n, 0) + n * c! * (c + 1) * (1/0! + 1/1! + ... 1/c!)
                     # = n * c! + n * c! * (c + 1) * O(e) = O(c * n * c!)
                    is_win = not self.canWin(s[:i] + '--' + s[i+2:])    # O(n) space
                    i += 1
            i += 1
        return is_win

@@ -1,8 +1,1145 @@
+# Time:  O(n + c%5E3 * 2%5Ec * logc)%0A# Space: O(c * 2%5Ec)%0A%0A# hash solution.%0Aclass Solution(object):%0A    def canWin(self, s):%0A        %22%22%22%0A        :type s: str%0A        :rtype: bool%0A        %22%22%22%0A        lookup = %7B%7D%0A%0A        def canWinHelper(consecutives):%0A            consecutives = tuple(sorted(c for c in consecutives if c %3E= 2))  # O(clogc)%0A            if consecutives not in lookup:%0A                # We have total O(2%5Ec) game strings,%0A                # each one has O(c) choices to the next one,%0A                # and each one would cost O(clogc) to sort,%0A                # so we get O((c * clogc) * 2%5Ec) = O(c%5E2 * 2%5Ec * logc) time.%0A                # To cache the results of all combinations, thus O(c * 2%5Ec) space.%0A                lookup%5Bconsecutives%5D = any(not canWinHelper(consecutives%5B:i%5D + (j, c-2-j) + consecutives%5Bi+1:%5D)%0A                                           for i, c in enumerate(consecutives)%0A                                           for j in xrange(c - 1))%0A            return lookup%5Bconsecutives%5D%0A%0A        # re.findall: O(n) time, canWinHelper: O(c) in depth%0A        return canWinHelper(map(len, re.findall(r'%5C+%5C++', s)))%0A%0A%0A
 # Time: 
@@ -1196,16 +1196,16 @@
 of %22++%22%0A
-
 # Space:
@@ -1342,17 +1342,16 @@
  depth.%0A
-%0A
 class So
@@ -1348,32 +1348,33 @@
 .%0Aclass Solution
+2
 (object):%0A    de

Update flip-game-ii.py