时间戳

首页 > 解决方案 > 在多维数组中找到 4 个连续相等字符的最佳方法是什么？

arrays - 在多维数组中找到 4 个连续相等字符的最佳方法是什么？

问题描述

挑战是用可能的最佳算法在水平、垂直或对角线方向上找到 4 个连续相等的字符。

例如，如果我们有这个矩阵：

[

['L','T','G','C', 'T','A' ],

['X','A','G', 'T', 'G', 'A' ],

['T','R', 'T', 'K','G', 'A' ],

['A', 'T', 'A','M','G', 'A' ],

[ 'C','C','C','C' ,'T','G'],

['V','C','D','C','T','W']

]

该算法应该找到AAAA（垂直），CCCC（水平）和TTTT（倒对角线）。

你会怎么做？可以使用任何编程语言。

提前致谢！

标签： arraysalgorithmperformanceoptimizationlogic

解决方案

这是一个用重复字符串修改的 Boogle 板问题。

我相信您可以及时解决O(N*M)：N列数和M：行数。

您可以做的方法是在已匹配字符串中具有内存并标记为已访问的 BFS。

在此链接中，您可以看到带有字典的实现。您需要进行修改才能获得重复的字符串o时间：https ://gist.github.com/davidreynolds/2865498

推荐阅读