最大可能的长方形字母
编写了一个程序来查找最大的字母矩形，这样每一行都形成一个单词(从左到右)，每个列形成一个单词(从上到下)。
我发现了这个有趣的问题。这不是家庭作业，虽然听起来可能是这样的。(我不在学校)。我这么做是为了好玩。
示例
从猫、汽车、猿、api、rep、提示中，我们得到了以下矩形(这是一个正方形)：
C a r a p=p
我最初的想法是构建某种前缀树，这样我就可以检索以特定字符串开头的所有单词。这将是有用的，当我们已经有2个或更多的单词(要么阅读从上到下或左到右)，我们需要找到下一个单词添加。
还有其他想法吗？
编辑
这能用长方体(三维矩形)来完成吗？
如果它需要在对角线上有有效的单词(idea信用:user645466)，那么它的algo将如何被优化呢？
回答 2
Stack Overflow用户
发布于 2011-12-14 23:26:13
给定长度的单词字典，创建两个新的词典:第一个词典包含所有单词的单个字母前缀(所有字母都可以是给定长度的单词的第一个字母)，第二个词典包含所有单词的双字母前缀(两个字母的所有序列都可以是给定长度的单词的前两个字母)。您也可以做三重前缀，但您可能不需要超越这一点。
- 从字典中选择一个单词，叫它
X。这将是矩阵的第一行。 - 使用您所做的方便的列表检查
X[1], X[2], ..., X[N]是否都是有效的单个字母前缀。如果是，继续执行步骤3；否则返回步骤1。 - 从字典中选择一个单词，命名为
Y。这将是矩阵的第二行。 - 检查
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)。。
其逻辑是一次生成一行单词的矩形，为行选择单词，然后检查列是否可以对单词完成。这比一次加一个字母要快得多。
Stack Overflow用户
发布于 2014-06-10 19:19:18
为相同长度=索引的单词创建一个Bag[]，然后创建一个尝试数组，每个长度的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;
}https://stackoverflow.com/questions/8512174
复制相似问题
腾讯云开发者
