394.字符串解码

一种独创的 不用辅助栈的解(笑)

lc394-shot

思路

不用栈 遍历字符串转 python 表达式 eval 直出

解题过程

对于 python，我们可用 eval 函数将一串字符串当作 python 语句直接执行

那么对于四个例子我们可以转换成代码中注释部分的表达式

1
2
3
4
eval('3*("a") + 2*("bc")')
eval('3*("a"+2*("c"))')
eval('2*("abc")+3*("cd")+"ef"')
eval('"abc"+3*("cd")+"xyz"')

复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def decodeString(self, s: str) -> str:
        func = '' # 用于存表达式
        for i in range(len(s)):
            if s[i].isdigit():
                if i > 0 and not s[i - 1].isdigit():
                    func += "+"
                func += s[i]
            elif s[i] == "[":
                func += "*("
            elif s[i] == "]":
                func += ")"
                if i < len(s) - 1 and s[i + 1] != "]" and not s[i + 1].isdigit():
                    func += "+"
            else:
                if i == 0 or not s[i - 1].isalpha():
                    func += '"'
                func += s[i]
                if i == len(s) - 1 or not s[i + 1].isalpha():
                    func += '"'
        print(func)
        return eval(func)