1-liner Python, Ruby


  • 30

    Python:

    Broken into several physical lines for readability, but still one logical line and just one simple statement.

    def partition(self, s):
        return [[s[:i]] + rest
                for i in xrange(1, len(s)+1)
                if s[:i] == s[i-1::-1]
                for rest in self.partition(s[i:])] or [[]]
    

    Ruby:

    def partition(s)
      s == '' ? [[]] : s.size.times.flat_map { |i| s[0..i] != s[0..i].reverse ? [] :
        partition(s[i+1..-1]).map { |rest| [s[0..i]] + rest }
      }
    end

  • 0
    O

    u r soooooo good at recursion


  • 13
    L

    Thank you very much. I learned a lot about Python from this code. But could you add some comments or break it down and add easy-to-understand version for your solutions? It will help newbies like me a lot.

    class Solution(object):
        def partition(self, s):
            ret = []
            for i in range(1, len(s)+1):
                if s[:i] == s[i-1::-1]:
                    for rest in self.partition(s[i:]):
                        ret.append([s[:i]]+rest)
            if not ret:
                return [[]]
            return ret

  • 0
    C
    This post is deleted!

  • 1
    C

    Thanks for sharing, This is my solution inspired by yours, it's a little bit faster with cache support :)

    def partition(self, s):
        def imp(s, cache):
            if not cache.has_key(s):
                ret = [[s[:i]] + item for i in xrange(1, len(s)+1) for item in imp(s[i:], cache) if s[:i] == s[i-1::-1]]
                cache[s] = ret if ret else [[]]
            return cache[s]
        return imp(s, {})

  • 0

    I'm not quite convinced it's really faster. First I did a practice test, submitted each five times:

    Mine: 180, 164, 184, 172, 176 => average 175 ms
    Yours: 168, 200, 180, 164, 148 => average 172 ms

    Not a significant difference.

    I'm not sure about it in theory. How about you? My gut feeling is that caching doesn't help much because I'm going over everything anyway and it doesn't matter much whether I get it from cache or recompute it. Caching does save some computation overhead, but it also introduces some organizational overhead. It would be different if we were dealing with some kind of "summary" instead of a complete list of possibilities. Then reusing already computed summary values would really help.


  • 1

    Well, if you learned a lot from it anyway, then maybe it didn't need comments or a simpler version :-D

    But yes, I know my solutions aren't always newbie-friendly. Though partly that's because I want people to see something unfamiliar and hopefully not run away but learn about it. And sometimes I do include simpler versions or explanations, sometimes even very detailed. Depends on how obvious I find it and on my current mood :-)


  • 0
    C

    hi StefanPochmann, I think for some extreme test cases, it's still necessary to use cache.
    I did a test with both solutions with "aaaaaaaaaaaaaaaaaaaaaa", here is the result:

    yours: 18.740
    mine: 4.639

    At least it doesn't harm too much to have a cache here, as the result itself claims a lot of memory already:)


  • 0
    R

    neat solution! can you explain the time complexity of it? thanks a lot :)


  • 0
    W

    @StefanPochmann
    sir, how did you measure your runtime?


  • 0

    @weiheng4 Like I said, I submitted each five times (in the LeetCode OJ, of course).


  • 0
    W

    @chris.zhang.336
    sir, how did you measure the runtime to a certain input?


  • -1
    W

    @StefanPochmann
    well, ok. but why they are different to the same code?


  • 0

    @weiheng4 Because the server isn't in the exact same state every time?


  • 1

    amazing as usual...
    here is my solution (beats 98%) with memo:

    class Solution(object):
        def partition_core(self, s):
            s_len = len(s)
            if self.memo[s_len]:
                return self.memo[s_len]
            res = []
            for i in range(len(s)-1, -1, -1):
                current = s[i:]
                if current==current[::-1]:
                    pre_res = self.partition_core(s[:i])
                    res += [r+[current] for r in pre_res]
            self.memo[s_len] = res
            return res
    
        def partition(self, s):
            self.memo = [None]*(len(s)+1)
            self.memo[0]=[[]]
            return self.partition_core(s)
    

  • 0
    S

    I'm your fan Stefan!!! Cheers!


  • 0
    Z

    I think I knew how to interpret the @StefanPochmann 's Ruby code.
    To understand the code:

    1. firstly: you should first understand what partition(s[i+1..-1]) do.
      Well, simple, it will return a correct answer with the string s[i+1..-1]. Let's use partitions_arr_i+1 to represent this answer. (plural is because answer usually contain many possible partitions).

    2. Secondly, you should understand why a .map { |rest| [s[0..i]] + rest } is applied to this result, by map { |rest| [s[0..i]] + rest }, s[0..i] is append in front of each partition in partitions_arr_i+1.

    3. Thirdly, think about what is s[0..i], let's see this map would happen if if s[0..i] == s[0..i].reverse, which means s[0..i] would always be a Palindrome!

    4. Finally, put the result together by flat_map. For instance, if s = "ababa", by s.size.times.flat_map, we have the i = 0..4, the result for each is:

      i = 0: [["a", "b", "a", "b", "a"], ["a", "b", "aba"], ["a", "bab", "a"]]
      i = 1: []
      i = 2: [["aba", "b", "a"]]
      i = 3: []
      i = 4: [["ababa"]]

    flat_map will put all those result to an array and flatten it (flatten(1) actually).

    Beautiful code, Cheers for you @StefanPochmann !

    it only spent me 5 hours lol.


  • 0
    D

    REALLY REALLY AMAZING !!


  • 0
    J
    This post is deleted!

  • 0

    I am always learning from your code. What an amazing recursion.


Log in to reply
 

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