java - 水平、垂直或对角线检测多个 4 个相同字母序列的最有效算法

Question

我被分配了一项任务来编写一个算法来检测给定的字符串数组是否包含多个水平、垂直或对角重复的 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 对角线发现 CCCC 水平线发现 GGGG 垂直线发现

因此，由于在此输入示例中找到了 1 个以上的序列，因此输出应该为真。

我有一个解决这个问题的想法，但我的主要问题是处理对角线，特别是使用一种有效的方法来解决这个问题，因为他们希望在高并发环境中使用这个函数。

我将不胜感激提供的任何帮助。如果有人不会编写代码也没关系，但至少有一些想法可以找到解决这个问题的正确方法。

我已经很感谢了！

标签： javastring

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 条长度为 4 的对角线。

既然我们只是可以满足长度要求的对角线，下一步就是简单地沿着对角线走，并将每个下一个值与起始值进行比较。为了进一步提高效率，我们可以在对角线不再与起始字符匹配时停止检查它。

这是它在代码中的一种表现方式：

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)