DFS | 判断是否为子矩阵

Posted on Edited on In Symbols count in article: 1.7k Reading time ≈ 2 mins.

题目来源于某次蔚来笔试~

本渣只能想到这一种方法！感觉好暴力啊！截至目前还没有想到更好的方法呜呜~但是这种方法是可以做的！

题目描述

有两个矩阵，矩阵1（m×m），矩阵2（n×n），判断矩阵2是不是矩阵1的子矩阵，若是输出Yes，若不是输出No

示例

1
2
3
4
5
6
7
8
9
10
11
12
const m1 = [
    ['#', '.', '#'],
    ['.', '#', '.'],
    ['#', '.', '#']
]

const m2 = [
    ['#', '.'],
    ['.', '#']
]

// 输出 'Yes'

解题思路

  • 设两个指针i和j，用于遍历m1，找到m1[i][j] === m2[0][0]

  • 设置指针a和b，用于遍历m2，同时i+a和j+b继续遍历m1

    • 设置边界
      • i+a >= m1.length || j+b >= m2.length 返回false
      • m1[i+a][j+b] !== m2[a][b] 返回false
    • 满足条件
      • a === m2.length -1 && b === m2.length -1， 返回true

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function fn(matrix1, matrix2) {
    const m = matrix1.length, n= matrix2.length;
    // 用于判断是否存在符合的情况
    let flag = false;    // 初始条件为false
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix1[i][j] === matrix2[0][0]) {
                if (dfs(i, j)) flag = true;  // 只要有一次满足，就可以~
            }
        }
    }
    return flag ? 'Yes' : 'No'; // 只要有一次满足，就为true，如果一次都没满足，就是false
    
    
    function dfs(i, j) {
        for (let a = 0; a < n; a++) {
            for (let b = 0; b < n; b++) {
                if (i+a >= n || j+b >= n || matrix1[i+a][j+b] !== matrix2[a][b]) return false;
            }
        }
        return true;
    }
}

测试一下~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// eg1
const m1 = [
    ['#', '.', '#'],
    ['.', '#', '.'],
    ['#', '.', '#']
]

const m2 = [
    ['#', '.'],
    ['.', '#']
]

console.log(fn(m1, m2)) // 'Yes'

// eg2
const m1 = [
    ['#', '.', '#'],
    ['.', '#', '.'],
    ['#', '.', '#']
]

const m2 = [
    ['#', '.'],
    ['#', '#']
]

console.log(fn(m1, m2))  // No