Short Python by converting into strings

  • 5

    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)

  • 0

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

  • 0

    Right, thanks for pointed that out, already fixed it by adding a prefix "^"

  • 0

    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?

  • 0

    @livelearn said in Short Python by converting into strings:

    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.

  • 0

    @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

  • 0

    @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?

  • 0

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

  • 0

    @realisking Can you post that code as text instead, so I can copy&paste it to play with it?

  • 0

    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
    def test(n):
        return "Done" * n in "WTF" * (n*10)
    for i in range(4,9):

  • 2

    @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?

    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),

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

  • 0

    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.

  • 0

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

    Knuth-Morris-Pratt is not sublinear

  • 0

    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:

  • 0

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

  • 0

    @zjlvmiao said in Short Python by converting into strings:

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

    No it's not.

  • 0
    This post is deleted!

Log in to reply

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