718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1:

输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3,2,1] 。

示例 2:

输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出:5

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100

算法思路:

考虑动态规划,dp[i][j] 表示字符串 text1中子串 [0, i - 1] 与字符串 text2 中子串 [0, j - 1] 的最长公共子序列的长度。递推公式如下:

  • 对于 i,j(i>=1,j>=1):
    • 如果 text1[i] == text2[j],则 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
    • 否则,dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
  • i==0,j==0时,即 dp[0][0]初始化为 0 。

代码实现:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(), len2 = text2.length();
        // dp[i][j]: 字符串 text1中子串 [0, i - 1] 与字符串 text2 中子串 [0, j - 1] 的最⻓公共⼦序列的长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 找到了⼀个公共元素,和其前面的 dp[i - 1][j - 1] + 1 取较大值
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                } else {
                    //不相同则取 dp[i][j - 1], dp[i - 1][j] 中较大值
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
}

Q.E.D.


以无限为有限,以无法为有法