在一个二维数组中查找特定模式的最佳方法

Question

在一个二维数组中查找特定模式的最佳方法

algorithmpuzzle

7

我有一个随机字符的二维数组。我想匹配这些字符的特定模式：例如：ABA、BACKA、向上/向下/向左/向右移动。找到这个模式的最佳算法是什么？

- Swami

这是一道面试题吗？ - Jake Kurzer

这不是面试问题，也不是作业。 - Swami

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dfb · Accepted Answer

如果这类似于单向词搜，即一旦开始向左，就只能继续向左前进，那么答案应该很简单，只需测试每个可能的起始位置并朝每个方向前进。在最坏情况下，对于一个n x n的矩阵，时间复杂度将为O(mn^2)。如果可以向上/向左/等任意次数移动，则最明显的方法是将矩阵视为图形，并进行BFS或DFS。根据单词的长度和字母的分布，这可能成本过高。

如果您对单个矩阵有多个查询，则通过在类似于Trie的结构中缓存生成的单词并引用原始单元格，可以加快这些方法的速度。