[leetcode 282]Expression Add Operators 原创解法

发表于 更新于

题目概述

原题链接

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (
not unary) +, -, or * between the digits so they evaluate to the target value.

 "123", 6 -> ["1+2+3", "1*2*3"] 
 "232", 8 -> ["2*3+2", "2+3*2"]
 "105", 5 -> ["1*0+5","10-5"]
 "00", 0 -> ["0+0", "0-0", "0*0"]
 "3456237490", 9191 -> []

首先想到的解法就是遍历所有的组合，一一计算比较排除。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution1(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        if num:
            result = []
            path = []
            n = len(num)
            self.find(num, 0, n, target, path, result)
            return result

    def find(self, num, begin, end, target, path, result):
        if begin == end:
            s = "".join(path)
            if self.is_valid(path) and eval(s) == target:
                result.append(s)
        else:
            path.append(num[begin])
            self.find(num, begin + 1, end, target, path, result)
            if begin < end - 1:
                path.append("+")
                self.find(num, begin + 1, end, target, path, result)
                path.pop()
                path.append("-")
                self.find(num, begin + 1, end, target, path, result)
                path.pop()
                path.append("*")
                self.find(num, begin + 1, end, target, path, result)
                path.pop()
            path.pop()

    def is_valid(self, path):
        flag = True
        tmp = ""
        for i in path:
            if i in "0123456789":
                tmp += i
            elif i in "+-*":
                if len(tmp) >= 2 and tmp[0] == '0':
                    flag = False
                    break
                tmp = ""

        if len(tmp) > 1 and tmp[0] == "0":
            flag = False

        return flag

分析

没有意外，这种解法超时了。

先不考虑eval()函数是否应该使用。 显然的情况是每一种字符组合至少遍历４遍。

  • 第一遍，得到组合
  • 第二遍，join
  • 第三遍，eval
  • 第四遍，is_valid排除

有办法使用动态规划么？把一个大问题替换成子问题进行求解。 比如先计算一个字符的所有的解。然后考虑增加到两个字符。在第一个字符的解 的基础上，考虑在两个字符中间插入加减乘。然后再在两个字符的解的基础上 再加入第三个字符。以此类推。这种方法，并没有减少计算量，其实还是遍历 所有的组合。然后得到最终的解。

那么最终我们可以选择的优化方向就是，使用深度优先遍历的时候，必须要在 遍历的同时，进行计算。这样当到达结束判断的时候，能够直接判断。

简化问题

为了便于分析，首先简化问题。考虑如何计算字符串”123”，并且 只允许插入加号或者不插入加号。

为了把问题组合描述为一个树的形式。我们把两个数字直接连接起来组成 一个新的数字，看做一个操作，定义为.，那么a.b = ab，而数值计算 的公式为a.b = a*10+b， 而且这个符号的优先级高于加号和乘号。 这样可得如下树图。

tree pic

根据这种假定，对于任意数字字符串n1n2n3，可以得到 的查找树如下图。

tree2 pic

通过的解法

这样我们有了解法２。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
class Solution2(object):
    def addOperators(self, num, target):
        """
        这个居然通过了。呵呵。不过是勉强通过的。
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        if num:
            end = len(num)
            result = []
            path = [num[0]]
            s1 = [int(num[0])]
            s2 = []
            begin = 1
            self.find(begin, end, num, s1, s2, path, target, result)
            return result
        else:
            return []

    def find(self, begin, end, num, s1, s2, path, target, result):
        if begin == end:
            if s1[0] == target:
                result.append("".join(path))
        else:
            ops = [("+", 10), ("-", 10), ("*", 20), (".", 30)]
            ps = ["+", "-", "*", ""]
            if begin + 1 < end:
                for i in range(4):
                    s11 = s1[:]
                    s22 = s2[:]
                    path.append(ps[i] + num[begin])
                    self.helper(begin, end, num, ops[i], path, result, s11, s22, target)
                    path.pop()
            elif begin + 1 == end:
                for i in range(4):
                    s11 = s1[:]
                    s22 = s2[:]
                    path.append(ps[i] + num[begin])
                    self.helper2(begin, end, num, ops[i], path, result, s11, s22, target)
                    path.pop()

    def helper(self, begin, end, num, op, path, result, s1, s2, target):
        # 没有到达结尾
        if s2:
            op_pre = s2[-1]
            if op_pre[1] < op[1]:
                # 需要压栈延迟计算
                s1.append(int(num[begin]))
                s2.append(op)
                self.find(begin + 1, end, num, s1, s2, path, target, result)

            else:
                # 需要先把s2出栈计算完成，直到栈中的符号级别小于当前。
                is_valid = True
                while s2:
                    op_pre = s2[-1]
                    if op_pre[1] < op[1]:
                        break
                    op_pre = s2.pop()
                    n2 = s1.pop()
                    n1 = s1[-1]
                    if op_pre[0] == "+":
                        s1[-1] = n1 + n2
                    elif op_pre[0] == "-":
                        s1[-1] = n1 - n2
                    elif op_pre[0] == "*":
                        s1[-1] = n1 * n2
                    elif op_pre[0] == "." and n1 != 0:
                        s1[-1] = n1 * 10 + n2
                    else:
                        is_valid = False
                        break
                if is_valid:
                    s1.append(int(num[begin]))
                    s2.append(op)
                    self.find(begin + 1, end, num, s1, s2, path, target, result)
        else:
            s1.append(int(num[begin]))
            s2.append(op)
            self.find(begin + 1, end, num, s1, s2, path, target, result)

    def helper2(self, begin, end, num, op, path, result, s1, s2, target):
        # 到达结尾
        if s2:
            op_pre = s2[-1]
            if op_pre[1] < op[1]:
                s1.append(int(num[begin]))
                s2.append(op)

                is_valid = True
                while s2:
                    op_pre = s2.pop()
                    n2 = s1.pop()
                    n1 = s1[-1]
                    if op_pre[0] == "+":
                        s1[-1] = n1 + n2
                    elif op_pre[0] == "-":
                        s1[-1] = n1 - n2
                    elif op_pre[0] == "*":
                        s1[-1] = n1 * n2
                    elif op_pre[0] == "." and n1 != 0:
                        s1[-1] = n1 * 10 + n2
                    else:
                        is_valid = False
                        break
                if is_valid:
                    self.find(begin + 1, end, num, s1, s2, path, target, result)
            else:
                is_valid = True
                while s2:
                    op_pre = s2[-1]
                    if op_pre[1] < op[1]:
                        break
                    op_pre = s2.pop()
                    n2 = s1.pop()
                    n1 = s1[-1]
                    if op_pre[0] == "+":
                        s1[-1] = n1 + n2
                    elif op_pre[0] == "-":
                        s1[-1] = n1 - n2
                    elif op_pre[0] == "*":
                        s1[-1] = n1 * n2
                    elif op_pre[0] == "." and n1 != 0:
                        s1[-1] = n1 * 10 + n2
                    else:
                        is_valid = False
                        break

                if is_valid:
                    s2.append(op)
                    s1.append(int(num[begin]))
                    while s2:
                        op_pre = s2.pop()
                        n2 = s1.pop()
                        n1 = s1[-1]
                        if op_pre[0] == "+":
                            s1[-1] = n1 + n2
                        elif op_pre[0] == "-":
                            s1[-1] = n1 - n2
                        elif op_pre[0] == "*":
                            s1[-1] = n1 * n2
                        elif op_pre[0] == "." and n1 != 0:
                            s1[-1] = n1 * 10 + n2
                        else:
                            is_valid = False
                            break

                    if is_valid:
                        self.find(begin + 1, end, num, s1, s2, path, target, result)
        else:
            n2 = int(num[begin])
            n1 = s1[-1]
            is_valid = True
            if op[0] == "+":
                s1[-1] = n1 + n2
            elif op[0] == "-":
                s1[-1] = n1 - n2
            elif op[0] == "*":
                s1[-1] = n1 * n2
            elif op[0] == "." and n1 != 0:
                s1[-1] = n1 * 10 + n2
            else:
                is_valid = False

            if is_valid:
                self.find(begin + 1, end, num, s1, s2, path, target, result)