@neverlandzzy No, it'll just be O(m + n). We would need O(m) and O(n) space for generating the preorder serialization string for tree1 and tree2 respectively. Since we're generating the serialization for both trees, we would need O(m + n) space.
Posts made by Ellest
RE: Subtree of Another Tree
@luckygirl - I think the author of this article may of taken string concatenation into account. I agree it should be O(m + n) for the serialization (preorder traversal) given we're optimizing the concatenation (i.e. StringBuilder in Java, string array then concatenation at end for Python, etc.)
Note that comparison can also be reduced to O(m) as we could use KMP string comparison to check if the serialization of t is a substring of the serialization of s
Concise Python DP O(mn) O(m) space with clear explanation
We can utilize DP as this problem has an optimal sub-structure. There are only two "direct" ways to reach a coordinate (r,c), from the left (r,c-1) and from above (r-1, c). This means that if we know the minimum HP needed to reach a certain coordinate (r,c), we can also deduce what minimum HP we need to start with for the direct left (r,c-1) and direct above coordinates (r-1, c). Using this notion, we can start a DP from the end coordinate (N-1, M-1) as there aren't any spaces left to traverse after we reach the ending coordinate, meaning the ending coordinate do not have any subproblems (i.e. if the end coordinate has a value of -5, we know we need at least 6 HP at either the direct left and direct above coordinates in order to reach the end coordinate).
With this in mind our DP equation is as follows:
dp[c] = min(dp[c+1], dp[c]) - dungeon[r][c]
We need to make sure that we at least have 1 HP at each coordinate. This can be enforced by setting the start of the DP (end coordinate) to be 1 if the value at the ending coordinate is positive.
We can optimize the dp solution further by using a rolling array as we only need subproblems from the level directly below to solve the problem at the current level.
def calculateMinimumHP(self, dungeon): M, N = len(dungeon), len(dungeon) row = [0 for _ in dungeon[-1]] row[-1] = max(1, -dungeon[-1][-1] + 1) for c in range(M-2, -1, -1): row[c] = max(row[c+1] - dungeon[-1][c], 1) for r in range(N-2, -1, -1): nxt, row[-1] = row[-1], max(row[-1] - dungeon[r][-1], 1) for c in range(M-2, -1, -1): nxt, row[c] = row[c], max(min(row[c+1], row[c]) - dungeon[r][c], 1) return row