LeetCode Expression Add Operators：SLR(1)、meet-in-the-middle及其他
题目描述
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.
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.
分析
枚举所有位置的符号(并置、+、-、*)后转化为表达式求值。加速的办法是让枚举和求值一起进行。
考虑题目要求的文法：
E ::= E "+" F | E "-" F
F ::= F "*" L
L ::= "0" | L1
L1 ::= "1" | ... | "9" | L1 "0" | ... | L1 "9"使用不考虑前导0的简化文法。我们会采用递归算法，形似recursive descent parser，在递归过程中不难采取一些措施避免生成前导0。
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：
+ + + +
/ \ / \ / \ / \
2 * 2 * 2 * + 6
/ \ / \ / \ / \
3 @ 3 @ * 6 2 *
/ \ / \ / \ / \
4 5 @ 6 3 @ 3 @
/ \ / \ / \
4 5 4 5 4 5我们给parse tree每个节点设置semantic value，即对应的表达式的结果。因为节点按照中序遍历顺序添加，任何左子树的结构不会再发生变化，可以把整棵子树收缩成一个节点。@是文法优先级最高，也可以规约，即把对应子树收缩。上面的四棵树收缩后变成下面这样：
+ + + +
/ \ / \ / \ / \
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+b*c\)与\(d*e+f\)合并得到\(a+b*cd*e+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+b*c+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)\)。
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;
}
};