arrays - 在矩阵中查找数组

Question

给定an array and a 2d matrix.您必须查找矩阵中是否存在数组。为此，您可以从矩阵中的任何点开始并进入4 directions，如果您在，(i,j)您可以进入(i+1,j), (i-1,j), (i,j+1), (i,j-1)。

如果数组存在，则返回索引的开始和结束对，否则返回 false。

假设给定的数组是[ 1, 10, 22, 47, 33, 10]，矩阵如下所示..那么我们可以看到数组存在于矩阵中，起点和终点分别是：(2,2) and (3,4) [ 0-based indexing]

解决此问题的技术之一是从矩阵中的每个单元格运行 DFS 并检查数组是否存在，但该方法将是O(n^4)（因为在每个 DFS 运行中可能有 n^2 次迭代）。

我的时间复杂度分析正确吗？我们还能做得比这更好吗？

标签： arraysmatrixgraphdynamic-programming

Answer 1

这是针对此问题的最优化解决方案...

let print = console.log

print("Result:", contain([1, 10, 22, 47, 33, 10], [
    [1, 2, 3, 5, 8],
    [6, 5, 10, 22, 47],
    [20, 21, 1, 54, 33],
    [45, 8, 6, 5, 10]
]));

function* findPoint(firstItem, matrix) {
    for (let y = 0; y < matrix.length; y++)
        for (let x = 0; x < matrix[y].length; x++)
            if (firstItem == matrix[y][x])
                yield [y, x]
}

function contain(path, matrix) {
    let startPoint = path.shift(), lastIndex = path.length - 1;
    main_loop: for (let [y, x] of findPoint(startPoint, matrix)) {
        print("find point:", startPoint, "coordinate:", [y, x]);
        loop: for (let i = 0; i < path.length; i++) {
            let point = path[i];
            // calculate sibling point: 
            for (let [_y, _x, dir] of [[y - 1, x, "up"], [y + 1, x, "down"], [y, x - 1, "left"], [y, x + 1, "right"]]) {
                // get item from matrix using point
                if (matrix[_y]?.[_x] != point) continue
                print("next point:", point, "Direction:", dir)
                if (lastIndex == i) return true
                y = _y, x = _x;
                // if sibling point matched, then update point and continue `root` loop
                continue loop;
            }
            print('point:', point, `didn't matched any sibling`);
            continue main_loop;
        }
    }
    return false
}

时间复杂度是线性的：O(n),