Basically we convert our
string representation, then just check whether substring exists in target string.
class Solution(object): def isSubtree(self, s, t): """ :type s: TreeNode :type t: TreeNode :rtype: bool """ def convert(p): return "^" + str(p.val) + "#" + convert(p.left) + convert(p.right) if p else "$" return convert(t) in convert(s)
Right, thanks for pointed that out, already fixed it by adding a prefix
Well this should be a slow solution considering we could be doing the str of a very large value, thus making the solution greater than O(n), but why does it run so fast?
Well this should be a slow solution considering we could be doing the str of a very large value, thus making the solution O(n^2), but why does it run so fast?
I agree if node number is given, when node values becomes larger, the converted string must be longer thus it would take "more" time but not very much. For a 32 bits number the biggest length is 10.
And what do you mean by O(n^2)? If n here refers to the length of converted string, this solution is O(n) then.
@realisking Oh good point, but say we do have the worst case where every number is length 10, I guess that would still be a O(n) solution
@realisking I'm pretty sure the complexity of
convert isn't O(#nodes), not even for best case scenarios.
Do you know the complexity of the
Thought should be O(n) for
in operation before, but there is no bad to find some evidence and let's do it.
And I did some experiments. Both in Python2 and 3.
For Python 2, here is what I got.
For Python 3, here is what I got.
We can see the time increasing linear with string size both in Python 2 and 3, thus yes, I think the complexity of the
in operation for string matching is O(n). Any further suggestion, Stefan?
BTW: I got an job offer as an algorithm engineer yesterday. It is only 10 months from I knew nothing about coding. I do really learn a lot from you, Stefan. Thank you so much and anytime if wanna have a vocation to Shanghai, everything is on mine. :)
@realisking Can you post that code as text instead, so I can copy&paste it to play with it?
import time def TIME(func): def wrapper(*args, **kwargs): t = time.time() ans = func(*args, **kwargs) t = time.time() - t return ans, t return wrapper @TIME def test(n): return "Done" * n in "WTF" * (n*10) for i in range(4,9): print(test(10**i))
@realisking That's not a good test. Your two strings are a best case scenario. They don't even have any characters in common. That makes the algorithm so fast that you're actually not measuring the
in operator but mostly the creation of the strings! Try preparing the strings beforehand. What times do you get for this?
@TIME def test(s, t): return s in t for i in range(4,9): n = 10**i print(test("Done" * n, "WTF" * (n*10)))
Here's a proper worst case, showing quadratic runtime:
>>> from timeit import timeit >>> for e in range(10, 16): n = 2**e print(timeit('s in t', 's = "a" * %d + "ba"; t = "aa" * %d' % (n, n), number=100)) 0.02283171976600329 0.08677567873640157 0.31249382161108485 1.2718506141431192 5.134004260046098 20.76774636109795
I didn't study the algorithm, but Martijn Pieters wrote about it last year and is likely correct saying "O(N) on average, O(NM) worst case".
And congrats for your job offer. I'm glad if my stuff helps people :-)
Another lesson, previously I thought we can achieve string matching by
KMP in O(n+k) thus there is no reason Python
in did worse than that. Then I just realized
KMP takes extra space while it would be stupid if
in did the same way.
Thanks for your reply and test as always.
Knuth-Morris-Pratt is not sublinear
Excuse me, what's the difference between the following two in Python? I got the difference answer. Thank you so much!
if (t1.left != t2.left) or (t1.right != t2.right): if t1.left is None != t2.left is None or t1.right is None != t2.right is None:
so the last line could be
return convert(t) in convert(s) if t else False
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.