最有效的算法可以水平，垂直或对角线检测多个相同字母的多个序列

Question

我已经分配了一个任务编写算法以检测给定的字符串阵列是否包含一个以上的4个序列，该序列在水平，垂直或对角线上都包含4个重复的字母。他们还问我最有效的方法。

输入示例就是这样：

String[] input = {"ATGCGA","CAGTGC","TTATGT","AGAAGG","CCCCTA","TCACTG"};

，但是你们可以更清楚地看到它的桌子：

A T G C G A
C A G T G C
T T A T G T
A G A A G G
C C C C T A
T C A C T G

此数组包含3个带有重复字母的序列：

AAAA被发现对角线水平发现CCCCGGGG垂直发现

因此，由于在此输入示例中发现了超过1个序列，因此输出应为true。

我有一个想法来解决这个问题，但我的主要问题是处理对角线，尤其是使用有效的方法来完成此问题，因为他们希望在高并发环境中使用此功能。

我将感谢提供的任何帮助。如果有人不能编写代码，但是至少有一些想法可以找到解决此问题的正确方法。

我已经很感激！

Answer 1

我认为您最好的选择是首先分析问题。

确定什么构成对角线。在这种情况下，随着对角线的穿越。

，行和列指数都增加了1。

接下来，您有一些必须执行的规则。基于对角线长度为4，有一个最大的行/列位置，任何对角线都可以启动。为了提高效率，您只能穿越可能导致匹配的指数。

为了视觉上，矩阵中的任何这些X位置都可以是重复序列的开始：

X X X O O O
X X X O O O
X X X O O O
O O O O O O
O O O O O O
O O O O O O

因此，对于具有36个字符的6x6矩阵，我们只会查看最多9个可能的对角线。

现在，我们只有可以符合长度要求的对角线，下一步就是简单地走下对角线并将每个值与起始值进行比较。为了提高效率，我们可以在不再匹配起始角色的情况下立即停止检查对角线。

这是它可能在代码中播放的一种方式：

public static void main(String ... args) {
    // Find diagonal duplicates (AAAA) starting at (0, 0)
    String[] input = {"ATGCGA","CAGTGC","TTATGT","AGAAGG","CCCCTA","TCACTG"};
    findSequences(input);
    // Find diagonal duplicates (AAAA) starting at (2,2)
    String[] input2 = {"BTGCGA","CCGTGC","TTATGT","AGAAGG","CCCCAA","TCACTA"};
    findSequences(input2);
    // Find diagonal duplicates (ZZZZ) starting at (1,2)
    String[] input3 = {"BTGCGA","CCZTGC","TTCZGT","AGAAZG","CCCCAZ","TCACTA"};
    findSequences(input3);
}

private static void findSequences(String ...input) {
    // sought-after length of repeated characters
    int repeatLength = 4;
    // max row a diagonal of length 'repeatLength' could start at
    int maxStartRow = input.length - repeatLength;
    // max column a diagonal could start at... assumes all rows have same length.
    int maxStartColumn = input[0].length() - repeatLength;
    for (int i = 0; i <= maxStartRow; i++) {
        for (int j = 0; j <= maxStartColumn; j++) {
            boolean allMatch = true;
            char[] sequence = new char[repeatLength];
            // Capture the starting character
            sequence[0] = input[i].charAt(j);
            // Walk down the diagonal from the starting character
            // ceasing when the characters no longer match or we exceed the length
            for (int diagonalCounter = 1; diagonalCounter < repeatLength && allMatch; diagonalCounter++) {
                sequence[diagonalCounter]= input[i+diagonalCounter].charAt(j+diagonalCounter);
                allMatch &= (sequence[0] == sequence[diagonalCounter]);
            }
            if (allMatch) {
                System.out.println("Match " + String.valueOf(sequence) + " found, starting at (" + i + ", " + j + ")");
            }
        }
    }
}

打印：

Match AAAA found, starting at (0, 0)
Match AAAA found, starting at (2, 2)
Match ZZZZ found, starting at (1, 2)