Python Generators solution


  • 11
    class NestedIterator(object):
    
        def __init__(self, nestedList):
            def gen(nestedList):
                for x in nestedList:
                    if x.isInteger():
                        yield x.getInteger()
                    else:
                        for y in gen(x.getList()):
                            yield y
            self.gen = gen(nestedList)
    
        def next(self):
            return self.value
    
        def hasNext(self):
            try:
                self.value = next(self.gen)
                return True
            except StopIteration:
                return False
    

    This assumes that the iterator is just used as described in the problem. Usually, hasNext should be both optional and idempotent, but a next+hasNext iterator is very unpythonic anyway, so I decided to not do that here, as I feel it would distract from the generator.

    And of course while this solution is (IMHO) somewhat cute, it passes each value through each level it's nested in, so it's not efficient.


  • 0
    S

    In the hasNext(), self.value = next(self.gen) sets the field value, however, next() returns self.value as well. In this recursion, where does the initial self.value comes from?


  • 0
    S

    In the hasNext(), self.value = next(self.gen) sets the field value, however, next() returns self.value as well. In this recursion, where does the initial self.value comes from?


  • 0

    Sorry, I don't understand what you mean. hasNext sets the value and then next uses it, that's it. And neither of them is recursive.


  • 1
    D

    i think you got confused by the next method between NestedIterator and generator. in the line "self.value = next(self.gen)" the next method is the generator's built in method and you can replace the line by "self.value = self.gen.next()". and if you want to use the next method of NestedIterator, you should write "self.value = self.next(self.gen)" but this won't work of course. and what's more, it's a good solution.


  • 0

    Ah, yeah, that's gotta be it. Thanks.


  • 0
    T

    do we need to check hasNext() inside next()?


  • 0
    S

    @duduainankai Thx for the clarification!


  • 1
    V

    @StefanPochmann I don't like the try except block too much above, as it assumes the order of function calls of hasNext() and next(). So I tried to use a count variable to keep track of remaining length.

    For some reason, it can't pass the case of empty input. Here is that case:

    Input: [[]]
    Output: 
    Expected: []
    

    Here is my code. Almost same as yours above. Could you please point out where my code is wrong? Thanks!

    class NestedIterator(object):
    
        def __init__(self, nestedList):
            self.count = len(nestedList)
            def gen(nestedList):
                for x in nestedList:
                    if x.isInteger():
                        self.count -= 1
                        yield x.getInteger()
                    else:
                        self.count += len(x.getList()) - 1
                        for y in gen(x.getList()):
                            yield y
            self.gen = gen(nestedList)
    
        def next(self):
            return next(self.gen)
    
        def hasNext(self):
            return self.count
    

  • 0

    @voiceup [[]] isn't empty. It does contain one inner list. So you set count to 1 even though there is no number anywhere.


  • 0
    S

    I modified it a bit so the hasNext() method is now idempotent

    class NestedIterator(object):
    
        def __init__(self, nestedList):
            self.peek = None
            def gen(nestedList):
                for x in nestedList:
                    if x.isInteger():
                        yield x.getInteger()
                    else:
                        for y in gen(x.getList()):
                            yield y
            self.gen = gen(nestedList)
    
        def next(self):
            if self.peek is None:
                return next(self.gen)
            else:
                tmp = self.peek
                self.peek = None
                return tmp
                    
    
        def hasNext(self):
            if self.peek is None:
                try:
                    self.peek = next(self.gen)
                    return True
                except StopIteration:
                    return False
            else:
                return True
    

Log in to reply
 

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