先假设没有问号。在最终的排列中，$\pi _i$ 能够等于 $j$ 当且仅当第 $i$ 列的后 $m-1$ 个字符等于第 $j$ 列的前 $m-1$ 个字符。我们建立一张图，节点表示所有长度为 $m-1$ 的字符串，每一列从前 $m-1$ 个字符组成的字符串向后 $m-1$ 个字符组成的字符串连边。问题转化为了用若干个环覆盖所有边。显然，在有解（即每个点的入度等于出度）时，方案数等于所有点出度阶乘的乘积。

在有问号时，由于每行最多一个问号，事实上只有三种情况：

• 无解。

• 可以确定所有问号代表的字符。

• 所有问号代表的字符相同。

在第三种情况中，可以枚举问号代表的字符，将方案数求和，再减掉算重的，即无论问号代表什么字符都合法的方案数乘 $(|\Sigma|-1)$。

枚举字符后可以用哈希快速比较字符串。时间复杂度 $O(nm+n|\Sigma|)$。