leetcode hot100 字符串解码

394. 字符串解码

已解答

中等

相关标签

相关企业

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

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

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

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

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """

        # 先得到对应关系
        hashmap_end={}
        stack=[]
        for index,str_t in enumerate(s):
            if str_t=='[':
                stack.append(index)
                hashmap_end[index]=-1
            elif str_t==']':
                end = stack[-1]
                hashmap_end[end]=index
                stack.pop()
            



        hashmap = {}
        for i in range(10):
            hashmap[str(i)]=i

        # print(hashmap_end)
        # print(hashmap)
        def func_t(start,end):
            i=start
            rt_str=""
            repeat_num=0
            while i<end:
        
                if hashmap.get(s[i])==None and s[i]!='[' and s[i]!=']':
                    rt_str+=s[i]
                    i+=1
                elif hashmap.get(s[i])!=None:
                    # 读取数字然后递归调用
                    repeat_num = repeat_num*10 + int(s[i])
                    i+=1
                elif s[i]=='[':
                    # reapeat = int(repreat_num)
                    # stack.append(i)
                    tmp = func_t(i+1,hashmap_end[i])
                    rt_str = rt_str + tmp*repeat_num
                    i = hashmap_end[i]+1
                    repeat_num=0
                else:
                    print(s[i])

            
            return rt_str  
        return func_t(0,len(s))

上述是我自己的解法，主要解决的是括号里面还有括号的情况，就用迭代的方法解决，每次都返回括号内的输出结果，在呈上次数，缺点是需要提前的把括号的前后index准备好。

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        
        def dfs(i):
            multi = 0
            res=""
            while i< len(s):
                if s[i]=="[":
                    i,tmp = dfs(i+1)
                    res = res + multi*tmp
                    multi=0
                elif  s[i]>='0' and s[i]<='9':
                    multi = 10*multi +int(s[i])
                    i+=1
                    
                elif s[i]==']':
                    
                    return i+1 , res
                else:
                    res+=s[i]
                    i+=1
            return res
        return dfs(0)

这个是标准代码，直接把所有的迭代放到一起了