本题就是一个暴力搜索,逐个将字母尝试匹配数字,没有问题的话就处理下一个字母,有问题的话就返回匹配其他数字。为了方便对齐,我们将所有字符串都逆序排列:
CBA
ED
F
----
IHG
我们dfs的顺序就是逐个处理CEFIBDHGA。当每一列的加数字符匹配完之后(比如说CEF),我们需要查验它们的sum是否与result(也就是I)对应的数字一致。我们需要考虑大致需要剪支的情况:
- I已经匹配过了,但是与sum不一致。
- I没有匹配过,但是sum已经匹配过其他字符了。
所以我们需要两个hash表,一个记录每个字符对应的数字,另一个记录每个数字是否已经被匹配过。
大致的递归函数的形式是:dfs(int i, int j, int sum)
,其中(i,j)表示我们在处理第i行、第j列的字符,试图给其赋值一个数字;sum表示该列当前的累加和。