矩阵最大对角线模式匹配

Question

我在做矩阵模式匹配的技术面试时遇到了一个问题。我能够使用蛮力解决问题，但想知道是否有更有效的解决方案，因为我只得到了大约一半的效率分数。预先感谢您的输入。

给定一个包含数字 0, 1, 2 和模式 [1, 2, 0, 2, 0, 2, 0] 的矩阵，找到从矩阵中的任意点开始的匹配模式的最大长度，但是只能沿对角线行驶。

这里是我们期望函数 return 12.

的示例

这里是我们期望函数 return 7.

并且空矩阵应该 return 0.

这是我的代码，正如我之前所说，它确实有效并通过了所有测试，但我得到了对接分数。

def max_diagonal_match(matrix) -> int:
    max_len = 0
    pattern_match = [1, 2, 0, 2, 0, 2, 0]
    for i in range(0, len(matrix)):
        for j in range(0, len(matrix[i])):
            max_len = max(
                max_len,
                find_i_minus_j_minus(matrix, i, j, pattern_match, 7),
                find_i_minus_j_plus(matrix, i, j, pattern_match, 7),
                find_i_plus_j_minus(matrix, i, j, pattern_match, 7),
                find_i_plus_j_plus(matrix, i, j, pattern_match, 7)
            )
    return max_len


# i-, j-
def find_i_minus_j_minus(matrix, i, j, pattern, mod):
    count = 0
    while i >= 0 and j >= 0:
        if matrix[i][j] != pattern[count % mod]:
            return count
        count += 1
        i -= 1
        j -= 1
    return count


# i-, j+
def find_i_minus_j_plus(matrix, i, j, pattern, mod):
    count = 0
    while i >= 0 and j < len(matrix[i]):
        if matrix[i][j] != pattern[count % mod]:
            return count
        count += 1
        i -= 1
        j += 1
    return count


# i+, j-
def find_i_plus_j_minus(matrix, i, j, pattern, mod):
    count = 0
    while i < len(matrix) and j >= 0:
        if matrix[i][j] != pattern[count % mod]:
            return count
        count += 1
        i += 1
        j -= 1
    return count


# j+, i+
def find_i_plus_j_plus(matrix, i, j, pattern, mod):
    count = 0
    while i < len(matrix) and j < len(matrix[i]):
        if matrix[i][j] != pattern[count % mod]:
            return count
        count += 1
        i += 1
        j += 1
    return count

非常感谢您抽出宝贵的时间阅读，非常感谢任何意见。

Answer 1

基于的接受答案。它基于几个关键思想：

您可以在一个范围内使用 np.diagonal 将每个可能的对角线切出数组。您可以翻转阵列以确保获得所有角度。

您可以 tile 图案以确保它至少与最大对角线一样长或更长。

您可以 zip 对角线和图案，由于 zip 的工作方式，图案中的额外值将自动删除。

然后你可以在压缩的(diag,pattern)上使用takewhile来检查有多少个连续匹配len(set(x))==1。

如果你对所有可能的组合都这样做并取最大值，你应该有答案。

import numpy as np
from math import ceil
from itertools import takewhile

def max_sequence(arr):
    solns = []
    i = arr.shape[0]
    for x in range(-i, i+1):
        values = arr.diagonal(x)
        N = len(values)
        possibles = np.where(values == pattern[0])[0]
        for p in possibles:
            check = values[p:p+N]
            m = len(list(takewhile(lambda x:len(set(x))==1, zip(pattern,check))))
            solns.append(m)
    return max(solns)

def find_longest(arr):
    if len(arr)>0:
        return max([max_sequence(x) for x in [arr, np.fliplr(arr), np.flipud(arr), arr[::-1]]])
    else:
        return 0

arr = np.array([
    [1,0,2,1,1,1,1,0,0,0,0,0,0],
    [1,2,2,1,1,1,1,0,0,0,0,0,0],
    [1,0,0,1,1,1,1,0,0,0,0,0,0],
    [1,0,0,2,1,1,1,0,0,0,0,0,0],
    [1,0,0,2,0,1,1,0,0,0,0,0,0],
    [1,0,0,1,1,2,1,0,0,0,0,0,0],
    [1,0,0,1,1,1,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,2,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0],
])

arr1 = np.array([
    [1,0,2,1,1,1,1],
    [1,2,2,1,1,1,1],
    [1,0,0,1,1,1,1],
    [1,0,0,2,1,1,1],
    [1,0,0,2,0,1,1],
    [1,0,0,1,1,2,1],
    [1,0,0,1,1,1,0]
])

arr2 = np.array([])

pattern = [1, 2, 0, 2, 0, 2, 0]
# Make sure pattern repeats longer than the max diagonal
pattern = np.tile(pattern,ceil(arr.shape[1] / len(pattern)))

for a in [arr, arr1, arr2]:
    print(find_longest(a))

输出

12
7
0

Answer 2

我们可以将问题分解为沿着矩阵的每条对角线寻找可能的最长匹配。然后算法的效率归结为我们可以多快找到沿任何给定对角线的最长匹配项。

对于长度为 N 的对角线和长度为 M 的图案，您的解决方案是 O(N^2)：您尝试沿对角线的每个 N 个起点，然后尽可能扩展匹配（即 O(N) 比较）

这个问题确实存在更快的解决方案。可以匹配每个对角线的复杂度：

O(NM) 通过使用动态规划，如果 M << N
O(NlogN) 通过对角线后缀的字典顺序排序（或相关技术：后缀树、Burrows-Wheeler 变换、FM 索引等）
从技术上讲，O(N) 可以使用后缀数组，但算法太复杂而无法在编码面试中实现（例如 Ukkonen 的算法）

还有一些算法，虽然 O(N^2) 在最坏的情况下，在实践中可能比这快得多，例如当很少有长匹配时，种子和扩展算法很快。

我确信上面提到的技术并不是一个详尽的列表。

矩阵最大对角线模式匹配

matrix maximum diagonal pattern match

python

python-3.x

algorithm

matrix

string-matching