我有一个随机字符的2D数组.我想匹配这些字符的特定模式:例如:ABA,BACKA,上/下/左/右.找到这种模式的最佳算法是什么？
如果这就像一个单词搜索，你只能向一个方向走（一旦你开始向左，你只能继续向左走），那么答案应该很简单，只需继续测试每个可能的起始位置并转到每个方向。在最坏的情况下，对于 n 的情况，这将是 O(mn^2) 如果您可以向上/向左/等任意次数，最明显的方法是将矩阵视为图形并执行 BFS 或 DFS。根据单词的大小和字母的分布，这可能成本太高。
如果您对单个矩阵有多个查询，则这两种方法都可以通过将生成的单词缓存在类似 trie 的结构中并引用原始单元格来加速。