EllysBulls

作者：刘子祯 汪乐平

关键词：字符串 搜索 $meet-in-the-middle$ $Trie$树

题目描述

给一个$n$个长度为$m$的字符串组成的数组$c$和一个$n$个自然数组成的数组$a$，求是否有且仅有一个长度为$m$的字符串$s$，满足$\forall 0\leq i < n$，都有$a[i]=\sum_{j=0}^{m-1}[c[i][j]==s[j]]$。

$1\leq n \leq 50$，$2\leq m\leq 9$，$0\leq a[i]\leq m$，所有字符串只包含数字。

算法一

这道题就是一个暴力搜索，使用dfs进行搜索，但是直接枚举所有情况肯定不行，这需要进行剪枝，然后才能通过。 剪枝是这样的： 如果当前已经确定的部分超出了一些字符串的符合个数，则说明这个字符串一定不是结果，就直接return，停止下一层递归。 如果在假定后面没搜到的字符都符合的情况下依然不够，也可以说明这不是结果，直接return，停止下一次递归。 排序，先枚举出现多的，再枚举出现少的。

算法二

额……搜索，复杂度还没有保证，这么不优美的算法怎么可能是最优算法呢？下面讲一种复杂度有保证的算法。

我们使用$meet-in-the-middle$。令$k=\lfloor \frac{m}{2}\rfloor$，枚举所有长度为$k$的数字串$s'$，对每个串求一个$n$元组$(x[0],x[1],...,x[n-1])$，其中$x[i]=\sum_{j=0}^{k-1}[c[i][j]==s'[j]]$。再枚举所有长度为$m-k$的数字串$s''$，对每个串求一个$n$元组$(y[0],y[1],...,y[n-1])$，其中$y[i]=\sum_{j=k}^{m-1}[c[i][j]==s''[j-k]]$。那么，如果我们能找到一对$s'$和$s''$，使得$(x[0]+y[0],x[1]+y[1],...,x[n-1]+y[n-1])=(a[0],a[1],...,a[n-1])$，则$s's''$是一个合法的解($s1s2$表示$s2$接在$s1$后面得到的字符串)。

所以我们要做的就是对于任意一个$s''$，求有多少个$s'$满足$(x[0],x[1],...,x[n-1])=(a[0]-y[0],a[1]-y[1],...,a[n-1]-y[n-1])$。我们把$n$元组看成字符串，用一棵$Trie$树来保存信息即可。求一次$x$和$y$的时间是$O(nm)$，一共有$10^{\lfloor \frac{m}{2}\rfloor}$个$s'$和$10^{\lceil \frac{m}{2}\rceil}$个$s''$，所以总的时间复杂度是$O(nm10^{\lceil \frac{m}{2}\rceil})$。如果用搜索求所有$s'$和$s''$，则时间复杂度可以降为$O(n10^{\lceil \frac{m}{2}\rceil})$。空间复杂度$O(nm10^{\lfloor \frac{m}{2}\rfloor})$。