718: 最长重复子数组

题解

1. 动态规划

通过一个二维数组arr[i][j]表示第一个字符串前i个字符和第二个字符串前j个字符组成的最长公共字符串的长度。

代码

function findLength(A: number[], B: number[]): number {
      // 基础版本
      // let ALen = A.length;
    // let BLen = B.length;
    // let arr = new Array(ALen + 1).fill(0).map(()=>new Array(BLen + 1).fill(0));
    // let max = 0;
    // for (let i = 1; i <= ALen; i++) {
    //     for (let j = 1; j <= BLen; j--) {
    //         if (A[i - 1] === B[j - 1]) {
    //             arr[i][j] = arr[i-1][j - 1] + 1;
    //         } else {
    //             arr[i][j] = 0;
    //         }
    //         max = Math.max(max, arr[i][j]);
    //     }
    // }
    // return max;
      // 优化版
    let ALen = A.length;
    let BLen = B.length;
    let arr = new Array(BLen + 1).fill(0)
    let max = 0;
    for (let i = 1; i <= ALen; i++) {
        for (let j = B.length; j > 0; j--) {
            if (A[i - 1] === B[j - 1]) {
                arr[j] = arr[j - 1] + 1;
            } else {
                arr[j] = 0;
            }
            max = Math.max(max, arr[j]);
        }
    }
    return max;
};

2. 滑动窗口

代码

// 计算红框的最大长度
function maxLen(M: number[], N: number[], i: number, j: number, len: number): number {
  console.log(M.slice(i),N.slice(j);
    let res: number = 0;
    let count: number = 0;
    for (let k = 0; k < len; k++) {
        if (M[i + k] === N[j + k]) {
            count++;
        } else {
            count = 0;
        }
        res = Math.max(res, count);
    }
    return res;
}
// 主函数
function findLength(A: number[], B: number[]): number {
    let a = A.length;
    let b = B.length;
    let ret = 0;
    for (let i = 0; i < a; i++) {
        let len = Math.min(b, a - i);
        let max = maxLen(A, B, i, 0, len);
        ret = Math.max(ret, max);
    }
    for (let i = 0; i < b; i++) {
        let len = Math.min(a, b - i);
        let max = maxLen(A, B, 0, i, len);
        ret = Math.max(ret, max);
    }
    return ret;
};

上图中console如下