3 lines Python, 2 lines Ruby, regular expression


  • 24

    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?


Log in to reply
 

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