arrays - 用于合并多个二维数组的一致行的高效算法

Question

我有任意数量的等宽但可能不等高的二维数组。它们可以由 1、0 或*可以匹配 1 或 0 的通配符组成。通配符始终位于相同的列中。我想同时返回与每个数组中至少一行一致的所有可能行，并且不包含通配符。

举一个具体的例子，考虑三个二维数组

     1 0 1 *        * 0 1 0        * 1 * 1    
a =  1 1 1 *   b =  * 1 1 0   c =  * 0 * 0
     0 1 0 *        * 0 0 1        

解决方案中的可能行可能是1 0 1 0. 与 的顶行a、顶行b、第二行一致c。相比之下，不应该在解决方案中的行是，因为尽管与 的底行和顶行一致，但0 1 0 1它与 的任何行都不一致。bac

除了进行低效的蛮力检查之外，我还很卡。似乎应该有更快的方法。是否有任何技巧可以帮助有效地解决这个问题？

标签： arraysalgorithm