My 2 lines solution in Python


  • 0

    Two lines of code:

    def reverseWords(self, s):
        for x, y in zip([-1] + [i for i, x in enumerate(s) if x == ' '] + [-1], [i for i, x in enumerate(s) if x == ' '] + [len(s)] * 2):
            s[x+1:y] = s[x+1:y][::-1]
    

    The simple version:

    def reverseWords(self, s):
        index = [i for i, x in enumerate(s) if x == ' ']
        for x, y in zip([-1] + index + [-1], index + [len(s)] * 2):
            s[x+1:y] = s[x+1:y][::-1]
    

    The idea is simple, find all space. Reverse all characters between the index (include 0 and len(s)). Then reverse whole string.

    For the 2 lines version, there must be some decent solution to generate the pair of index.


  • 0
    I

    Just curious, the question asked "not to use extra space", so your

    index = [i for i, x in enumerate(s) if x == ' ']
    

    is not an extra space? This algorithm seems to me a space complexity O(n) solution where the question asked for space O(1) solution?


  • 0

    I think actually not to use extra space in Python is unpractical. Even simple operation like this: s[x+1:y] = s[x+1:y][::-1] will use extra space.

    The range() in Python also use extra space.


  • 0
    I

    I think you're right, but if we use xrange() in python2 and range() in python3 (which uses generator), maybe we can define it as space O(1)?
    Let's assume the above is true, then using a single str variable and then loop through the given string one using xrange() might be actually space O(1)?
    Anyway, I don't think OJ would catch this~lol


  • 0

    Sure, but actually the xrange also need O(n) space. It just lazy eval.

    It's possible that we declare an variable and use while in Python that can satisfy O(1) space requirement, but it will become ugly and same as Java/C code.


  • 1

    If you're allocating that much extra space anyway, you might as well go all out :-)

    def reverseWords(self, s):
        s[:] = ' '.join(''.join(s).split()[::-1])

  • 0
    C

    When I just use s instead of s[:] I got wrong answer for my submission, can you tell me why?


  • 0

    Because you're then not modifying the list referenced by s. Instead, you only make s reference the new string. And s is only a local variable.


  • 0
    R

    what does s[:] mean? and what does s[:] = ' '.join(''.join(s).split()[::-1]) mean ?


  • 0

    It's just a slice, from start to end of s. And then I assign to it the sequence on the right. Really not much different from what you do in your own solution (s[start:n] = ...).


Log in to reply
 

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