Python Clean Regex Solution with Analysis


  • 0
    L

    Analysis

    1. the key is to find the minimal unit (i.e. 3[abc]) to spread out. Regular expression was born to identify patterns in string.
    2. we replace the unit with the expanded string, e.g.
      2[3[abc]] ==> 2[abcabcabc]
      Then we repeat 1 and 2 until no such unit exists.

    Code

    import re
    class Solution(object):
        def decodeString(self, s):
            regex = r"(\d+\[[a-z]+\])"
            match = re.search(regex, s)
            while match is not None: 
                # match '3[abc]'
                ss = s[match.start():match.end()]
                
                # match '3'
                r1 = '\d+'
                m1 = re.search(r1, ss)
                ss1 = ss[m1.start():m1.end()]
                
                # match 'abc'
                r2 = '[a-z]+'
                m2 = re.search(r2, ss)
                ss2 = ss[m2.start(): m2.end()]
                
                # replace '3[abc]' with 'abcabcabc'
                sss = int(ss1) * ss2
                s = s.replace(ss, sss)
                
                # do it again
                match = re.search(regex, s)
                
            return s
    

Log in to reply
 

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