leetcode [394] 字符串解码

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

s = “3[a]2[bc]”, 返回 “aaabcbc”. s = “3[a2[c]]”, 返回 “accaccacc”. s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.

class Solution:
    def decodeString(self, s: str) -> str:
        if s == '' or '[' not in s and ']' not in s:
            return s
        # find number
        k1, k2 = 0, 0
        while k1 < len(s) and s[k1] not in '0123456789':
            k1 += 1
        k2 = k1 + 1
        while k2 < len(s) and s[k2] in '0123456789':
            k2 += 1
        
        # find left [
        i = k2
        while i < len(s) and s[i] != '[':
            i += 1
        # find right ]
        j = i + 1
        # # of left [
        left = 1
        while j < len(s):
            if s[j] == ']':
                left -= 1
                if left == 0:
                    break
            if s[j] == '[':
                left += 1
            j += 1
        res = s[:k1] + int(s[k1:k2]) * self.decodeString(s[i + 1: j]) + self.decodeString(s[j + 1:])
        return res