LeetCode Expression Add Operators:SLR(1)、meet-in-the-middle及其他

题目描述

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.

1
2
3
4
5
6
Examples:
"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 -> []

Credits:
Special thanks to @davidtan1890 for adding this problem and creating all test cases.

分析

枚举所有位置的符号(并置、+-*)后转化为表达式求值。加速的办法是让枚举和求值一起进行。

考虑题目要求的文法:

1
2
3
4
E ::= E "+" F | E "-" F
F ::= F "*" L
L ::= "0" | L1
L1 ::= "1" | ... | "9" | L1 "0" | ... | L1 "9"

使用不考虑前导0的简化文法。我们会采用递归算法,形似recursive descent parser,在递归过程中不难采取一些措施避免生成前导0。

1
2
3
E ::= E "+" F | E "-" F
F ::= F "*" L
L ::= "0" | ... | "9" | L "0" | ... | L "9"

Parse tree以0~9为叶子,+-、并置(下面用@表示)为内部节点,其最右节点到根的距离小于等于3,之后会说明原因。对于某一前缀的parse tree,添加一个符号和一个数字后会得到一棵新的parse tree,这一过程可以看作在二叉树中添加一中序遍历序号最大的节点(类似于Cartesian tree线性构造算法)。取决于添加的符号,可能有以下三种变化。最左边为原先的parse tree,后面三棵为添加不同符号后得到的parse tree:

1
2
3
4
5
6
7
8
9
+ + + +
/ \ / \ / \ / \
2 * 2 * 2 * + 6
/ \ / \ / \ / \
3 @ 3 @ * 6 2 *
/ \ / \ / \ / \
4 5 @ 6 3 @ 3 @
/ \ / \ / \
4 5 4 5 4 5

我们给parse tree每个节点设置semantic value,即对应的表达式的结果。因为节点按照中序遍历顺序添加,任何左子树的结构不会再发生变化,可以把整棵子树收缩成一个节点。@是文法优先级最高,也可以规约,即把对应子树收缩。上面的四棵树收缩后变成下面这样:

1
2
3
4
5
+ + + +
/ \ / \ / \ / \
2 * 2 * 2 * 137 6
/ \ / \ / \
3 45 3 456 135 6

文法中的三个产生式有层级关系,高优先级符号的子树中没有低优先级符号,这就是任意节点到根距离小于等于3的原因。从另一个角度看,LR(0)项集是无圈的,最长路径长度为3。枚举并求parse tree的过程很像SLR(1),又像Earley parser。

-可以看作+,同时把右边的数字视为相反数。这样,我们得到的tree只剩下+ *两种操作符。+*都有单位元,若最右路径没有*,可以补上一个左孩子为1的节点;若没有+,可以补上一个左孩子为0的节点。这样保证了最右节点到根的距离恒为2,且树中有三个叶子,三个semantic values。

以上解释了三个semantic values可以刻画状态的原因。从左到右枚举各个位置上的符号,不难得到一个边枚举边求值的算法,枚举量为$O(4^n)$。常见优化技巧是meet-in-the-middle,即两边同时枚举到中间,把一边枚举的结果记录下来,另一边枚举到相遇时查表。用上这一技巧后,该算法很像packrat parser。倘若题目引入括号,那么LR(0)项集就含圈了,最右节点到根的距离就没有限制,3个semantic values就不够刻画状态。

注意相遇时要合并两边的部分结果。下面逐一考虑。

+相遇比较容易。假设左边部分的和为$s$,那么从右边部分找和为$target-s$的式子即可。

-相遇类似。

@相遇,合并时两边都得用到三个semantic values,$a+bc$与$de+f$合并得到$a+bcde+f$,难以计算,不存在有效的查表方法。因此我们不处理@相遇,放置并置符号后,交给递归调用的函数在之后相遇。若之后出现了+-,那么相遇过程就延迟到那时进行;若没有出现,则在全式末尾进行。

*相遇,若像@那么不处理,考虑枚举量。设从右到左的有$nn$个操作符待枚举,预处理表的枚举量为$O(4^{nn})$。从左到右的枚举量为$O(4^{n-nn})$,每一项得在右边记录集合中查表。因为*@两种符号都没处理相遇,还得考虑延迟相遇的情况数,为$O(2^{nn})$。若查表时间为常数,那么总的枚举量为$O(4^{nn}+4^{n-nn}*2^{nn})$。根据该式算得$nn$取$n/3$时枚举量最小,考虑到查表的代价,实际取值应在$n/3$与$n/2$之间。

处理*相遇需要用到两个semantic values,把左边部分在最后一个加号处断开(-可以转化为+),得到$a+b$的形式,右边在第一个加号处断开,得到$c+d$的形式,拼接得到$a+bc+d$。我们希望它等于$target$,即$b*c+d=target-a$。也就是说,对于右边两个semantic values $c$和$d$所表示的直线$y=cx+d$,我们希望它经过点$(b,target-a)$。

于是问题转化为:给出$O(4^{nn})$个点、$O(4^{n-nn})$根直线,对于每个点求经过它的直线。不妨设$nn$取$n/2$。一种思路是借助spatial data structure。若能在$O(4^{n/2}A)$的时间内计算,那么总的时间复杂度为$O(4^{n/2}+4^{n/2}A)$。考虑把点组织成K-d tree,对每根线逐一查询,$A$不小于$O(\sqrt{4^{nn/2}})$,不优于不处理*相遇。更好的方法可能是把点和线批量处理。若$A$为$O(\log{4^{n/2}})=O(n)$,则总的时间复杂度为$O(n*2^n)$。

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
typedef long long ll;
class Solution {
string a;
int n, nn, target;
vector<multimap<ll, string>> e_plus, e_minus;
vector<string> res;
void backward(int k, string s, ll add, ll mul, ll last, ll ten) {
if (k < nn) return;
int x = a[k-1]-'0';
ll ten2 = 10*ten, sum = add+mul*last;
backward(k-1, string(1, a[k-1])+s, add, mul, last+ten2*x, ten2);
if (ten == 1 || last >= ten) { // `last` has no leading zero
backward(k-1, string(1, a[k-1])+'*'+s, add, mul*last, x, 1);
backward(k-1, string(1, a[k-1])+'+'+s, sum, 1, x, 1);
backward(k-1, string(1, a[k-1])+'-'+s, add-mul*last, 1, x, 1);
e_plus[k].insert(make_pair(sum, s));
e_minus[k].insert(make_pair(add-mul*last, s));
}
}
void forward(int k, string s, ll add, ll mul, ll last) {
ll sum = add+mul*last;
if (k == n) {
if (sum == target)
res.push_back(s);
return;
}
int x = a[k]-'0';
if (last) // no leading zero
forward(k+1, s+a[k], add, mul, last*10+x);
forward(k+1, s+'*'+a[k], add, mul*last, x);
if (k < nn) {
forward(k+1, s+'+'+a[k], sum, 1, x);
forward(k+1, s+'-'+a[k], sum, -1, x);
} else {
auto rg = e_plus[k].equal_range(target-sum);
for (auto it = rg.first; it != rg.second; ++it)
res.push_back(s+'+'+it->second);
rg = e_minus[k].equal_range(target-sum);
for (auto it = rg.first; it != rg.second; ++it)
res.push_back(s+'-'+it->second);
}
}
public:
vector<string> addOperators(string num, int target) {
a = num;
n = a.size();
if (n) {
nn = n/2; // 0 < nn < n
this->target = target;
e_plus.resize(n);
e_minus.resize(n);
backward(n-1, string(1, a[n-1]), 0, 1, a[n-1]-'0', 1);
forward(1, string(1, a[0]), 0, 1, a[0]-'0');
}
return res;
}
};