题解 | #最长公共子序列(一)#

最长公共子序列(一)

题目描述

给定两个字符串 s1 和 s2，长度为m和n 。求两个字符串最长公共子序列的长度。

所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car" 、 "aaae" 则不是它的子序列。

所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。

方法一：动态规划方法

解题思路

对于本题目的求解，利用动态规划，dp[i][j]表示s1长度为i，s2长度为j时的最长公共子序列的长度。我们将dp数组初始化为0，然后两层循环遍历s1和s2中每一字符。如果当前字符相等，则有$dp[i+1][j+1]=dp[i][j]+1dp[i+1][j+1]\; =\; dp[i][j]+1$。否则有$dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])dp[i+1][j+1]\; =\; max(dp[i][j+1],\; dp[i+1][j])$。

解题代码

import java.util.*;

public class Solution {
    public int LCS (String s1, String s2) {
        //转化为字符数组
        char[] arr1=s1.toCharArray();
        char[] arr2=s2.toCharArray();
        int m=arr1.length;
        int n=arr2.length;
        //dp[i][j]表示s1、s2长度分别为i、j时对应的最长公共子序列长度
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(arr1[i]==arr2[j])
                {
                    //如果相等，则由之前的最长公共子序列加1
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                else
                {
                    //否则取dp[i][j+1]、dp[i+1][j]两者中较大值
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

复杂度分析

时间复杂度：两层循环，因此时间复杂度为$O(N\ast M)O(N*M)$，其中N，M分别为s1，s2的长度。

空间复杂度：使用二维dp数组，因此空间复杂度为$O(N\ast M)O(N*M)$，其中N，M分别为s1，s2的长度。

方法二：优化的方法

解题思路

我们可以对上面的方法进行优化，每次当前字符相等时，只与前一个最大长度的状态有关，因此可以利用滚动变量的思想，记录上一次的最大长度的状态，此时只需要一维的dp数组。

解题代码

import java.util.*;

public class Solution {
    public int LCS (String s1, String s2) {
        //转化为字符数组
        char[] arr1=s1.toCharArray();
        char[] arr2=s2.toCharArray();
        int m=arr1.length;
        int n=arr2.length;
        //dp[i]表示s2长度为i时，与s1的最长公共子序列长度
        int[] dp=new int[n+1];
        for(int i=0;i<m;i++)
        {
            //记录之前的最长公共子序列的长度
            int pre=0;
            for(int j=0;j<n;j++)
            {
                int cur=dp[j+1];
                //如果相等，则由之前的最长公共子序列加1
                if(arr1[i]==arr2[j])
                {
                    dp[j+1]=pre+1;
                }
                //如果不等，取两者较大者
                else
                {
                    dp[j+1]=Math.max(dp[j],dp[j+1]);
                }
                pre=cur;
            }
        }
        return dp[n];//返回结果
    }
}

复杂度分析

时间复杂度：两层循环，因此时间复杂度为$O(N\ast M)O(N*M)$，其中N，M分别为s1，s2的长度。

空间复杂度：申请一维dp数组，因此空间复杂度为$O(N)O(N)$。