leetcode_394

发表于   |   分类于

Decode String

题目戳这

题意

给定一个字符串形式，让你进行编码，具体的编码方式见样例。

解法

只能说我一直对这种题目搞不太清楚。。没有细分化的思维能力。。

简单快速的方法是用栈来代替递归形式，具体的就是通过压入栈中一个二元组[str,int]，首先是str代表的是括号内的字符串，但是我们知道这个字符串刚开始是不知道的，所以我们先默认其为””,int是括号外代表重复次数的数字，这是知道的。然后进入括号以后，如果没遇到’]’，则把字符压入栈顶二元组的str中去，直到遇到了’]’，则弹出栈顶二元组[string,int]。然后将string重复int次形成的字符串压入此时栈顶二元组的str中去，这样我们就形成了逐层的构建关系。。

再就是用递归的方法，用一个全局变量self.id来存储当前字符串处理到的位置，，这个写的比较繁琐，，速度也很慢。。

代码

非递归版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stk = []
        stk.append(["",1])
        nm = ""
        for x in s:
            if x.isdigit():
                nm += x
            elif x == '[':
                stk.append(["",int(nm)])
                nm = ""
            elif x == ']':
                string, num = stk.pop()
                stk[-1][0] += string*num
            else:
                stk[-1][0] += x
        return stk[0][0]

递归版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def dfs(self,s):
        res = ""
        while self.id < len(s):
            if s[self.id] == ']':
                break
            if s[self.id].isalpha():
                res += s[self.id]
                self.id += 1
            else:
                nm = ""
                while self.id<len(s) and s[self.id].isdigit(): # 算出数字
                    nm += s[self.id]
                    self.id += 1
                nm = int(nm) if nm else 0
                self.id += 1    # 跳过'['
                tmp = self.dfs(s)
                self.id += 1    # 跳过']'
                res += nm*tmp
        return res
        pass
    
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        self.id = 0
        return self.dfs(s)