Title address (394. String decoding)

Leetcode-cn.com/problems/de…

Topic describes

Given an encoded string, return its decoded string. The encoding rule is k[encoded_string], indicating that the encoded_string inside the square brackets is repeated exactly K times. Note that k is guaranteed to be a positive integer. You can assume that the input string is always valid; There are no extra Spaces in the input string, and the input square brackets are always formatted. In addition, you can assume that the raw data does not contain numbers, and that all numbers represent only the number of repetitions k, such as no input like 3a or 2[4]. Example 1: Input: S = "3[a]2[BC]" Output: "aaABCBC" Example 2: Input: S = "3[A2 [c]]" Output: "Accaccacc" Example 3: Input: S = "2[ABC]3[CD]ef" Output: "Abcabccdcdcdef" Example 4: Input: s = "abc3[CD]xyz" Output: "abccdcdcdXYZ"Copy the code

Train of thought

Through a temporary stack, the string in the stack is counted backwards starting with the] symbol and concatenated

code

  • Language support: Python3

Python3 Code:


class Solution:
    def decodeString(self, s: str) - >str:
        sList = list(s)
        stack = list()
        res = ""
        while len(sList) ! =0:
            i = sList.pop(0)
            # print(i)
            if i == "]":# the stack
                tempStr = ""Find the last string in the stack []
                while True:
                    j = str(stack.pop())
                    if j.isalpha() == True:
                        tempStr = j + tempStr
                    elif j == "[":
                        break
                tempInt = ""Find the last consecutive number in the stack
                # print(stack, tempStr, tempInt,"-")
                while True:
                    try:
                        k = stack.pop()
                        if k.isnumeric() == True:
                            tempInt = k + tempInt
                        else:
                            stack.append(k)If it is not a number, push it again
                            break
                    except:# for boundary conditions
                        break
                # print(stack,tempStr,tempInt)
                stack.append(tempStr*int(tempInt))
                # print(stack)
            else:
                stack.append(i)
                # print(stack)
        return "".join(stack)



if __name__ == '__main__':
    # s = "3[a]2[bc]"
    # s = "3[a2[c]]"
    # s = "2[abc]3[cd]ef"
    # s = "abc3[cd]xyz"
    s = "100[leetcode]"
    result = Solution().decodeString(s)
    print(result)

Copy the code

Complexity analysis

Let n be the length of the array.

  • O(nlogn)O(nlogn)O(nlogn)
  • Space complexity: O(n)O(n)O(n)