Skip to content

Latest commit

 

History

History
 
 

1307.Verbal-Arithmetic-Puzzle

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1307.Verbal-Arithmetic-Puzzle

本题就是一个暴力搜索,逐个将字母尝试匹配数字,没有问题的话就处理下一个字母,有问题的话就返回匹配其他数字。为了方便对齐,我们将所有字符串都逆序排列:

CBA
ED
F
----
IHG

我们dfs的顺序就是逐个处理CEFIBDHGA。当每一列的加数字符匹配完之后(比如说CEF),我们需要查验它们的sum是否与result(也就是I)对应的数字一致。我们需要考虑大致需要剪支的情况:

  1. I已经匹配过了,但是与sum不一致。
  2. I没有匹配过,但是sum已经匹配过其他字符了。

所以我们需要两个hash表,一个记录每个字符对应的数字,另一个记录每个数字是否已经被匹配过。

大致的递归函数的形式是:dfs(int i, int j, int sum),其中(i,j)表示我们在处理第i行、第j列的字符,试图给其赋值一个数字;sum表示该列当前的累加和。