1035. Uncrossed Lines

[Tcdian]

1035. Uncrossed Lines

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

Example 1

Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will
intersect the line from A[2]=2 to B[1]=2.

Example 2

Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3

Example 3

Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2

Note

• 1 <= A.length <= 500
• 1 <= B.length <= 500
• 1 <= A[i], B[i] <= 2000

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var maxUncrossedLines = function(A, B) {
    const cache = new Map();
    function findMaxUncroseLines(i, j) {
        const key = `${i}-${j}`;
        if (cache.has(key)) {
            return cache.get(key);
        }
        if (i < A.length && j < B.length) {
            let useCurrentI = -Infinity;
            let noUseCurrentI = -Infinity;
            const nextJIndex = B.indexOf(A[i], j);
            noUseCurrentI = findMaxUncroseLines(i + 1, j);
            if (nextJIndex >= 0) {
                useCurrentI =  findMaxUncroseLines(i + 1, nextJIndex + 1) + 1;
            }
            const maxLines = Math.max(noUseCurrentI, useCurrentI);
            cache.set(key, maxLines);
            return maxLines;
        }
        return 0;
    }
    return findMaxUncroseLines(0, 0);
};

• TypeScript Solution

var maxUncrossedLines = function(A: number[], B: number[]): number {
    const cache: Map<string, number> = new Map();
    function findMaxUncroseLines(i: number, j: number): number {
        const key = `${i}-${j}`;
        if (cache.has(key)) {
            return cache.get(key) as number;
        }
        if (i < A.length && j < B.length) {
            let useCurrentI = -Infinity;
            let noUseCurrentI = -Infinity;
            const nextJIndex = B.indexOf(A[i], j);
            noUseCurrentI = findMaxUncroseLines(i + 1, j);
            if (nextJIndex >= 0) {
                useCurrentI =  findMaxUncroseLines(i + 1, nextJIndex + 1) + 1;
            }
            const maxLines = Math.max(noUseCurrentI, useCurrentI);
            cache.set(key, maxLines);
            return maxLines;
        }
        return 0;
    }
    return findMaxUncroseLines(0, 0);
};