找到二維數組中的特定模式的最佳方法

Question

我有隨機字符的二維數組。 我想匹配這些字符的特定模式：例如：ABA，BACKA，上/下/左/右。 找到這種模式的最佳算法是什麼？

Answer 1

如果這就像是一個單詞搜索，你只能走一個方向（一旦你開始左邊，你只能繼續向左），答案應該非常簡單，只要繼續並測試每一個可能的開始位置和走向每個方向。在最壞的情況下，對於一個n乘n，這將是O（mn^2）。如果你可以任意多次上去/離開/ etc，最明顯的方法就是像矩陣一樣對待矩陣並執行BFS或DFS。根據單詞的大小和字母的分佈，這可能太昂貴了。

如果您對單個矩陣有多個查詢，則可以通過在類似trie的結構中對生成的單詞進行高速緩存並加入對原始單元格的引用來加速這兩種方法。