最大可能的字母矩形

Question

编写一个程序来找到最大可能的字母矩形,这样每行形成一个单词(从左到右),每一列形成一个单词(从上到下).

我发现了这个有趣的问题.这不是家庭作业,尽管听起来可能如此.(我不在学校).我这样做是为了好玩.

例

从cat,car,ape,api,rep,tip我们得到以下矩形(这是一个正方形):

c a r
a p e
t i p

我最初的想法是构建一种前缀树,以便我可以检索以特定字符串开头的所有单词.当我们已经有2个或更多单词(从上到下或从左到右阅读)并且我们需要找到要添加的下一个单词时,这将非常有用.

还有其他想法吗？

编辑

这可以用长方体(3D矩形)来完成吗？

如果它需要在对角线上有有效的单词怎么办(想法信用:user645466); 如何优化它的算法？

Answer 1

设D是字典.修复m和n.我们可以将寻找m×n矩形的问题表达为约束满足问题(CSP).

x _i,1 ... x _i, n∈D∀i∈{1,...,m}
x _1,j ... x _m, j∈D∀j∈{1,...,n}
x _i,j∈ {A, ...,Z}∀i∈{1,...,m},∀j∈{1,...,n}

解决CSP的一种非常常见的方法是将回溯与约束传播相结合.松散地说,回溯意味着我们选择一个变量,猜测它的值,并用一个较少的变量递归地求解子问题,约束传播意味着试图减少每个变量的可能性数量(可能为零,这意味着没有解决方案).

例如,我们可以通过选择x _1,1 = 来启动3×3网格Q.

Q??
???
???

使用英语词典时,x _1,2和x _2,1的唯一可能性是U(在拼字游戏"单词"之前).

解决CSP的技术是在回溯和约束传播之间取得平衡.如果我们根本不传播约束,那么我们只是使用蛮力.如果我们完美地传播约束,那么我们不需要回溯,但是运行本身解决NP难问题的传播算法可能相当昂贵.

在这个问题中,除非我们有良好的数据结构支持,否则在每个回溯节点处使用大型字典将变得昂贵.我将概述一种快速使用trie或DAWG来计算字母集的方法,通过该字母集,前缀可以扩展为完整的单词.

在每个回溯节点,我们分配的变量集是Young tableau.换句话说,在分配了它上面和左边的变量之前,不会分配任何变量.在下图中,.表示已分配的变量,*并?表示未分配的变量.

.....*
...*??
...*??
..*???
*?????

标记的变量*是下一个被赋值的候选者.拥有多个选择而不是每次选择固定变量的优点是某些变量排序可能比其他变量好得多.

对于每个*,在trie/DAWG中进行两次查找,一次用于水平,一次用于垂直,并计算下一个可以出现的字母组的交集.一个经典策略是选择具有最少可能性的变量,以期更快地达到矛盾.我喜欢这种策略,因为当有一个零可能性的变量时它自然地修剪,当有一个变量时它自然地传播.通过缓存结果,我们可以非常快速地评估每个节点.