Python Backtracking Solution


  • 0
    Z

    Even for this question backtracking is not a easy way to solve it. But it still a way to solve this question and indeed it beat 50%.

    First thing

    we need to simplify question to add two linkedlist with same length.
    this would be easy to do

            def add(l1,l2):
                if not l1:
                    return (None,0)
                else:
                    node,carry = add(l1.next , l2.next)
                    tmp = ListNode((l1.val + l2.val + carry)%10)
                    tmp.next = node
                    return [tmp,(l1.val + l2.val + carry)/10]
    

    Second thing

    So now we all need to do is to add two linkedlist!
    let say if we have two ls
    1 -> 2 -> 3 + 1 -> 2 -> 3 then all we need to is to call add function
    since they have same length

    BUT, if there it is two list we different length, we need to process so it works with this methos:
    lets say we have :
    1 -> 2 -> 3 -> 4 -> 5 + 2 -> 1
    first we should break long list into two part
    P1 : 1 -> 2 -> 3
    P2 : 4 -> 5

    By doing this, there is a part we can call add to calculate , which is

    2 -> 1+ 4 -> 5 return 6 -> 6

    Now the only thing left is P1 : 1 -> 2 -> 3
    So we can just link them together with 1 -> 2 -> 3-> (link) 6 -> 6

    Ha! we get the answer, but the real truggle is we have some data like

    1 -> 2 -> 3 -> 8 -> 8 + 2 -> 1
    So the same method will not work due to 8 -> 8 + 2 -> 1 will have a carry

    What we have to do is to use the idea of back tracking , so the alg is

    node,val = backtracking(` 2 -> 3 -> 8 -> 8`,` 2 -> 1`)
    return carry = (node.val) + val/10
    

    Another struggle is find out which is one long list except find the length of two list.

    class Solution(object):
        def addTwoNumbers(self, l1, l2):
           ###add number with same length 
            def add(l1,l2):
                if not l1:
                    return (None,0)
                else:
                    node,carry = add(l1.next , l2.next)
                    tmp = ListNode((l1.val + l2.val + carry)%10)
                    tmp.next = node
                    return [tmp,(l1.val + l2.val + carry)/10]
    
            ####break long list into two part 
            h1,h2 = l1,l2
            p1,p2 = None,None
            s = ListNode(0)
            while h1 and h2:
                h1 = h1.next
                h2 = h2.next
            if h1:
                s.next = l1
                tmp = l1
                while h1.next:
                    h1 = h1.next
                    tmp = tmp.next
                p1 = tmp.next
                tmp.next = None
                p2 = l2
            elif h2:
                s.next = l2
                tmp = l2
                while h2.next:
                    h2 = h2.next
                    tmp = tmp.next
                p1 = tmp.next
                tmp.next = None
                p2 = l1
            if not p1:
                p1,p2 = l1,l2
            print "p1",p1
            print "p2",p2
            print s
            ###end of break long list into two part ///////
    
            ###put two list back to one and return it
            def foo(ls):
                if not ls.next:
                    node,c = add(p1,p2)
                    ls.next = node
                    car =  (ls.val + c) /10
                    ls.val = (ls.val + c) %10
                    return car
                tmp = ls
                c = foo(tmp.next)
                print "!" , ls , c
                car = (ls.val + c)/10
                ls.val = (ls.val + c) %10
                return car
            c = foo(s)
            if not s:
                return s.next
            return s
    

Log in to reply
 

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