string - 在二维矩阵中排列 3 个字母的单词，使得每一行、每一列和对角线形成一个单词

Question

给你一本包含 3 个字母的单词的字典，你必须找到一个 3x3 的矩阵，使得每一行、每一列和对角线在字典中形成一个单词。字典中的单词已排序，您可以假设 O(1) 时间用于从字典中检索单词。

这已作为 Facebook 面试问题提出。

Answer 1

我的做法是先过滤字典，创建两个新字典:第一个包含所有单字母前缀的单词(大概有26个)，第二个包含所有双字母前缀的单词(其中有小于 26^2，因为没有单词以 BB 开头，例如)。

1. 从字典中选择一个词，命名为X。这将是矩阵的第一行。

2. 使用您制作的便捷列表检查X1、X2、X3 是否都是有效的单字母前缀。如果是，继续第 3 步；否则返回步骤 1。

3. 从字典中选择一个词，命名为Y。这将是矩阵的第二行。

4. 使用您制作的便捷列表检查X1 Y1、X2 Y2、X3 Y3 是否都是有效的双字母前缀。如果是，继续第 5 步；否则返回第 3 步。如果这是字典中的最后一个单词，则一直返回到第 1 步。

5. 从字典中选择一个单词，将其命名为Z。这将是矩阵的第三行。

6. 检查 X1 Y1 Z1, X2 Y2 Z2, X3 Y3 Z3 都是字典中的单词。如果是，恭喜，你已经做到了!否则返回第 5 步。如果这是字典中的最后一个单词，则一直返回到第 3 步。

我在 Maple 中对此进行了编码，并且运行良好。我让它运行以找到所有这样的矩阵，结果证明有足够的内存溢出导致 Maple 崩溃。