3 lines Python, 2 lines Ruby, regular expression


  • 26

    Python

    def decodeString(self, s):
        while '[' in s:
            s = re.sub(r'(\d+)\[([a-z]*)\]', lambda m: int(m.group(1)) * m.group(2), s)
        return s
    

    Submitted once, got accepted in 32 ms.

    Ruby

    def decode_string(s)
      1 while s.gsub!(/(\d+)\[([a-z]*)\]/) { $2 * $1.to_i }
      s
    end
    

  • 1

    @StefanPochmann the magic of regexps :)


  • 2
    H

    Amazing, I remember you!


  • 1
    T

    I was wondering how you handled nested balanced brackets (3[a2[c]]) with regex, but now I see, you work from the inside out.


  • 0
    A

    Similar, with 2 lines in Python:

       def decodeString(self, s):
            """
            :type s: str
            :rtype: str
            """
            found = re.search("(\d+)\[([a-z]+)\]",s)
            return self.decodeString(s[:found.start()]+ found.group(2)*int(found.group(1))+s[found.end():]) if found else s
    

  • 1

    hey bro. You are alway smart.
    Do you know any good ways to encode a string into this form?
    Like aaaarcaarc into 2[a]2[2[a]rc]
    Thank you


  • 0

    @zyoppy008 That's a pretty bad encoding, three characters longer than the original string :-P

    I hope encoding to minimal encoded representation will appear as another problem. Will probably use some dynamic programming then.


  • 0
    D

    @StefanPochmann
    One of my friend encounter this question during Google interview. The follow up question was to encode the string, the encoded string should be as short as possible.

    I couldn't pull up the answer. I only have this high level idea where we recursively find the most repeated pattern and encode it from bottom up.

    Really appreciate if you can help out.


  • 0
    H

    @TWiStErRob The regexp will try to find a match from index 0 of the target string. For your example, we can see when matching arrives index 4, where the char is a [, it violates the regexp. The 1st round of matching failed, it will start matching again from index 1, and repeat matching until find a match. Following this pattern, you can see 2[c] will be the first match.


  • 0
    H

    Thanks for the solution, I am always afraid of using regexp, since I can't make efficient regexp every time... Here's my JavaScript solution using regexp.

    var decodeString = function(s) {
        let re = /(\d+)\[([a-z]*)\]/, tmp;
        while(!!(tmp = re.exec(s)))
            s = s.replace(re, tmp[2].repeat(parseInt(tmp[1], 10)));
        return s;
    };
    

  • 0

    @StefanPochmann said in 3 lines Python, 2 lines Ruby, regular expression:

    y bad encoding, three characters longer than the original string :-P
    I hope encoding to minimal encoded representation will appear as another problem. Will probably use some dynamic programming then.

    Thank you. I still get no idea how to solve it, even defining the problem as encode a string into these form to get the minimal string.


  • 0
    P

    can anyone explain what the python code is really doing?


  • 0
    A

    Hi @StefanPochmann, while I always enjoy the conciseness of your code, I feel that it it sometimes unclear and it obscures the reasoning behind the code.


  • 0
    L

    @StefanPochmann said in 3 lines Python, 2 lines Ruby, regular expression:
    amazing!!!
    Have you read the python.org?
    How could I use the python like you?


  • 0
    T

    Just well done.
    Same thing but a little more readable and without the globals:

    
    continue while s.gsub!(/(\d+)\[([a-z]*)\]/)  { |num_str, chars|  chars * num_str.to_i }
    

    [Edit] sorry this was wrong, stick with
    next while s.gsub!(/(\d+)\[([a-z]+)\]/) { $2 * $1.to_i }


  • 1

    @the1pro Ooh, I like continue while. And yes, giving the match values names is nice. Not sure whether I didn't know that that's possible (I'm a Ruby noob) or whether I just wanted short code...


  • 0
    T

    @StefanPochmann a noobie sir, you are not.
    My suggestion was
    a) wrong (should have been next not continue, and it simply does not work)
    b) taken from mr Batsov's blog


  • 0
    M

    very amazing!


  • 1
    M

    How do I calculate the time complexity of this solution?


  • 0
    S

    Elegant solution to use regular express to solve the problem inside out!


Log in to reply
 

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