最长公共子序列

1143. 最长公共子序列

难度中等

字节面试题

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• 输入的字符串只含有小写英文字符。

动态规划

状态转移方程如下：

$dp[i][j] = dp[i-1][j-1]+1 \space\space\space\space\space\space\space text.charAt(i)==text.charAt(j)$

$dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) \space\space\space\space\space\space text.charAt(i)!=text.charAt(j)$

状态转移表：

	a	c	e
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // dfs(text1,text2,0,0,0);
        int n=Math.max(text1.length(),text2.length());
        int n1=text1.length();
        int n2=text2.length();
        int dp[][]=new int[n1][n2];
		
        // 边界条件
        if(n1==0||n2==0)return 0;
        dp[0][0] = text1.charAt(0)==text2.charAt(0)?1:0;
		// 第一个字符串的第一个字符和第二个字符串的所有字符
        for(int i=1;i<n1;i++){
            if(text2.charAt(0)==text1.charAt(i))dp[i][0]=1;
            else dp[i][0]=dp[i-1][0];
            // System.out.println(dp[i][0]);
        }
        // 第二个字符串的第一个字符和第二个字符串的第一个字符
        for(int j=1;j<n2;j++){
            if(text1.charAt(0)==text2.charAt(j))dp[0][j]=1;
            else dp[0][j]=dp[0][j-1];
            // System.out.println(dp[0][j]);
        }
		// 除了边界字符之外的所有字符
        for(int i=1;i<n1;i++){
            for(int j=1;j<n2;j++){
                // 相同时，由左上角的那个元素+1
                // 不同时，由左边和上边的最大值决定
                if(text1.charAt(i)==text2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }    
                // System.out.println(dp[i][j]);
            }
        }

        return dp[n1-1][n2-1]; 
    }
}

赏

谢谢你请我吃糖果

微信