🌵835. Image Overlap
https://leetcode.com/problems/image-overlap/
js
function maxOverlap(A, B) {
const rows = A.length
const cols = A[0].length
let max_overlap = 0
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
const A_overlap = A.slice(i).map(r => r.slice(j))
const B_overlap = B.slice(0, rows - i).map(r => r.slice(0, cols - j))
let overlap = 0
for (let x = 0; x < A_overlap.length; x++) {
for (let y = 0; y < A_overlap[0].length; y++) {
overlap += (A_overlap[x][y] & B_overlap[x][y])
}
}
if (overlap > max_overlap) {
max_overlap = overlap
}
}
}
return max_overlap
}
/**
* @param {number[][]} A
* @param {number[][]} B
* @return {number}
*/
var largestOverlap = function(A, B) {
return Math.max(maxOverlap(A, B), maxOverlap(B, A))
}py
class Solution:
def maxOverlap(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: int
"""
rows = len(A)
cols = len(A[0])
max_overlap = 0
for i in range(rows):
for j in range(cols):
A_overlap = [row[j:] for row in A[i:]]
B_overlap = [row[:cols - j] for row in B[:rows - i]]
overlap = [A_overlap[x][y] and B_overlap[x][y] for x in range(
len(A_overlap)) for y in range(len(A_overlap[0]))]
overlap = sum(overlap)
if overlap > max_overlap:
max_overlap = overlap
return max_overlap
def largestOverlap(self, A, B):
return max(self.maxOverlap(A, B), self.maxOverlap(B, A))