11

编写一个程序，找出最大可能的字母矩形，使每一行构成一个单词（从左到右），每列构成一个单词（从上到下）。

我发现了这个有趣的问题。这不是家庭作业，尽管听起来可能是这样。（我不在学校）。我这样做是为了好玩。

例子

从cat , car , ape , api , rep , tip我们得到以下矩形（正方形）：

c a r
a p e
t i p

我最初的想法是构建某种前缀树，这样我就可以检索所有以特定字符串开头的单词。当我们已经有 2 个或更多单词（从上到下或从左到右阅读）并且我们需要找到下一个要添加的单词时，这将很有用。

还有其他想法吗？

编辑

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

如果它需要在对角线上有有效的单词怎么办（创意来源：user645466）；如何优化它的算法？

4

3 回答 3

12

令 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-hard 问题的传播算法运行起来可能相当昂贵。

在这个问题中，除非我们有良好的数据结构支持，否则在每个回溯节点使用大型字典会变得很昂贵。我将概述一种方法，该方法使用trie或DAWG快速计算前缀延伸到完整单词的字母集。

在每个回溯节点，我们分配的变量集是一个 Young 表。换句话说，在它上面和左边的变量被赋值之前，没有变量被赋值。在下图中，.表示已分配变量，*和?表示未分配变量。

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

标记的变量*是下一个被赋值的候选变量。有多个选择而不是每次都选择一个固定变量的好处是，一些变量排序可能比其他的要好得多。

对于每个*，对 trie/DAWG 进行两次查找，一次查找水平方向，一次查找垂直方向，并计算接下来可能出现的字母集的交集。一种经典的策略是选择可能性最小的变量，希望我们更快地达到矛盾。我喜欢这种策略，因为当变量的可能性为零时，它会自然地修剪，而当变量的可能性为零时，它会自然地传播。通过缓存结果，我们可以非常快速地评估每个节点。

于 2011-12-15T04:22:12.413 回答
1

给定给定长度的单词字典，创建两个新字典：第一个包含单词的所有单字母前缀（可以是给定长度单词的第一个字母的所有字母），第二个包含所有双字母前缀单词（两个字母的所有序列，可以是给定长度的单词的前两个字母）。您也可以使用三重前缀，但您可能不需要超出此范围。

  1. 从字典中选择一个单词，调用它X。这将是矩阵的第一行。

  2. 使用您制作的方便列表检查X[1], X[2], ..., X[N]所有有效的单字母前缀。如果是，请继续第 3 步；否则返回步骤 1。

  3. 从字典中选择一个单词，调用它Y。这将是矩阵的第二行。

  4. 使用您制作的方便列表检查X[1] Y[1], X[2] Y[2], ...X[N] Y[N]是否都是有效的双字母前缀。如果是，继续第 5 步；否则返回第 3 步。如果这是字典中的最后一个单词，则一直返回第 1 步。

    ...

    2（N-1）。从字典中选择一个单词，调用它Z。这将是矩阵的第 N 行。

    2N。检查X[1] Y[1] ... Z[1], X[2] Y[2] ... Z[2], ...,X[N] Y[N] ... Z[N]是字典中的所有单词。如果是的话，恭喜你，你做到了！否则返回步骤 2(N-1)。如果这是字典中的最后一个单词，则一直回到步骤 2(n-3)。

逻辑是一次建立一行单词的矩形，为行选择单词，然后检查该列是否可以完成单词。这将比一次添加一个字母快得多。

于 2011-12-14T23:26:13.740 回答
1

为相同长度的单词创建一个 Bag[] = index 然后创建一个 Trie 数组，每个长度的 wordList 一个 Trie

   Rectangle makeRectangle(length, height, rectangle)
    {
        if ( length == rectangle.length()) check if complete and return;
        checkIfPartialComplete - check columns for valid prefixes
        for ( i from 1 to grouplist[i-1])
        {
            newRectangle = append word[i] to rectangle 
            return makeRectangle(l,h, rectangle with appended word) if not equal to null
        }
    }


boolean checkPartial(int l, Trie trie)
{
    for ( int i =0 ; i < l; i++)
    {
        String col = getColumn(i);
        if (!trie.contains(col))
        {
            return false;
        }
    }
    return true;
}
boolean checkComplete(int l, Bag<String> lengthGroup)
{
    for ( int i=0; i < l ; i++)
    {
        String col = getColumn(i);
        if (!lengthGroup.contains(col))
        {
            return false;
        }
    }
    return true;
}
于 2014-06-10T19:19:18.090 回答