我的 Word Puzzle 解决方案的时间复杂度？更好的解决方案？

Question

char[][] puzzle = new char[][] {
           // 0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16 
    new [] { 'T', 'S', 'T', 'N', 'E', 'S', 'E', 'R', 'P', 'D', 'N', 'L', 'L', 'A', 'M', 'S', 'G' },
    new [] { 'T', 'O', 'P', 'P', 'E', 'R', 'P', 'I', 'N', 'E', 'W', 'I', 'H', 'R', 'E', 'D', 'R' },
    new [] { 'O', 'T', 'E', 'V', 'I', 'T', 'S', 'E', 'F', 'C', 'O', 'G', 'R', 'E', 'R', 'N', 'E' },
    new [] { 'F', 'R', 'E', 'S', 'H', 'C', 'U', 'T', 'E', 'O', 'D', 'H', 'A', 'T', 'A', 'A', 'E' },
    new [] { 'D', 'D', 'N', 'A', 'T', 'S', 'I', 'G', 'T', 'R', 'G', 'T', 'T', 'A', 'I', 'L', 'N' },
    new [] { 'O', 'S', 'N', 'A', 'O', 'F', 'R', 'H', 'A', 'A', 'N', 'S', 'S', 'W', 'V', 'R', 'I' },
    new [] { 'E', 'S', 'N', 'N', 'M', 'A', 'G', 'A', 'R', 'T', 'I', 'F', 'I', 'C', 'I', 'A', 'L' },
    new [] { 'S', 'E', 'A', 'O', 'L', 'E', 'G', 'N', 'A', 'E', 'K', 'C', 'H', 'R', 'Y', 'G', 'S' },
    new [] { 'A', 'T', 'M', 'S', 'I', 'I', 'N', 'O', 'I', 'T', 'A', 'R', 'B', 'E', 'L', 'E', 'C' },
    new [] { 'H', 'T', 'S', 'R', 'E', 'T', 'T', 'T', 'R', 'D', 'T', 'M', 'A', 'A', 'N', 'S', 'S' },
    new [] { 'C', 'I', 'S', 'T', 'A', 'L', 'A', 'A', 'S', 'R', 'E', 'R', 'G', 'A', 'R', 'E', 'E' },
    new [] { 'R', 'N', 'E', 'P', 'O', 'F', 'D', 'R', 'E', 'T', 'L', 'C', 'C', 'I', 'H', 'R', 'L' },
    new [] { 'U', 'G', 'K', 'I', 'R', 'I', 'E', 'E', 'O', 'Y', 'R', 'Y', 'E', 'C', 'F', 'E', 'G' },
    new [] { 'P', 'U', 'I', 'N', 'T', 'U', 'L', 'E', 'E', 'C', 'D', 'I', 'N', 'M', 'S', 'T', 'L' },
    new [] { 'N', 'P', 'A', 'I', 'U', 'O', 'C', 'T', 'R', 'N', 'E', 'A', 'K', 'N', 'B', 'A', 'S' },
    new [] { 'E', 'D', 'O', 'I', 'T', 'R', 'N', 'E', 'A', 'T', 'R', 'D', 'I', 'S', 'E', 'E', 'G' },
    new [] { 'E', 'N', 'S', 'C', 'E', 'N', 'T', 'C', 'R', 'B', 'M', 'T', 'A', 'R', 'N', 'Y', 'R' } };

    String[] words = new String[] {
"ANGEL", "ARTIFICIAL", "BRANCHES", "CANDY CANES", "CELEBRATION", "DECEMBER", "DECORATE", "DECORATIONS", 
"FESTIVE", "FRESHCUT", "GARLAND", "GIFTS", "GREEN", "LARGE", "LIGHTS", "NEEDLES", "ORNAMENTS",
"PINE", "PRESENTS", "PURCHASE", "REAL", "SCENT", "SETTING UP", "SKIRT", "SMALL", "SPRUCE", "STAND", "STAR", "TAKING DOWN",
"TINSEL", "TOPPER", "TRADITION", "TREE FARM", "TREE LOT", "TRUNK", "WATER", "YEARLY", "HELLO WORLD"
};

拼图存储在二维数组中，单词存储在数组中。确定拼图中有多少个单词。一个词可以是垂直的、水平的或对角线的。

可以从char[]创建字符串，所以一行是一个字符串。然后我可以使用 string.IndexOf 方法来查找该行是否包含给定的单词。

因此我需要转换拼图以在各个方向查找单词。

水平变换():

AB => BA
光盘数据中心

垂直变换():

    AB => 交流电
    光盘光盘

对角变换():

    AB => C
    光盘广告
          乙

Here is the C# code 带有测试用例和良好的输出.

现在我计算时间复杂度。假设拼图的大小为n*n，字数为m，字的平均长度为a。

string.IndexOf 需要 O(a+n)。 string.IndexOf 对每个单词和每一行调用：O(mn(a+n)).

所以我的解的时间复杂度是O(mn(a+n))。我对么？你有更快的解决方案吗？

Answer 1

很可能你是对的。因为 a 是一个 const，那么 IndexOf 可以取 O(a + n) 或 O(a × n)，但是这两个估计等价于 O(n)。如果简化 big-O 表达式，它需要 O(m × n²).

似乎不可能开发出更快的算法。考虑一个简单的情况：我们需要找到单词第一个字母的所有出现。矩阵中的字母数量与n²成比例增加。对于 m 个单词，它在任何情况下都需要 O(m × n²)。

我的 Word Puzzle 解决方案的时间复杂度？更好的解决方案？

Time complexity of my solution to Word Puzzle? Better Solution?

c#

algorithm

time-complexity