# Short Python by converting into strings

• Basically we convert our `tree` into `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)
``````

• Fails for example `s = [12]`, `t = [2]`. (fixed now)

• @StefanPochmann
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 `in` operation?

• @StefanPochmann
Thought should be O(n) for `in` operation before, but there is no bad to find some evidence and let's do it.

Let's see what I got, here and here.

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?

• @StefanPochmann
My pleasure.

``````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 :-)

• @StefanPochmann
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.

• @realisking The original post btw gave a different reason against KMP:

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:
``````

• it's expected `False` when `t=[]`...
so the last line could be `return convert(t) in convert(s) if t else False`

• it's expected `False` when `t=[]`...

No it's not.

• This post is deleted!

• 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)
``````

Although it's O(n^2), but your solution is still faster than mine, which also is O(n^2). I think using string does help in Python. I'm glad that you got a job offer as an algorithm engineer. I can't imagine me learning code for just 10 months can land a job like that.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.