Python with stack


  • 0
    G
    • ans keeps the inner-most constructed string up to the current ] character
    • the last element of cnt keeps the count of current ans
    • the last element of part keeps the prefix string before the current ans.

    For example,
    when the cursor ^ is at the following position

    2[a3[b]c]
        ^
    

    before pushing to cnt and part, we have n=3, ans=a.
    when the cursor is at the following position

    2[a3[b]c]
          ^
    

    we have ans=b, part[-1]=a.

    class Solution(object):
      def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        part = []
        cnt = []
        n = 0
        ans = ''
        s = '1[{0}]'.format(s)
        for ch in s:
          if ch.isdigit():
            n = n*10 + ord(ch)-ord('0')
          elif '[' == ch:
            cnt.append(n)
            n = 0
            part.append(ans)
            ans = ''
          elif ']' == ch:
            ans = part.pop() + ans*cnt.pop()
          else:
            ans += ch
        return ans
    

Log in to reply
 

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