Make writing a habit together! This is the 7th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

The title

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.

A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none).

For example, “ace” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”. A common subsequence of two strings is a subsequence that is shared by both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3Copy the code

Explanation: The longest common subsequence is “ace”, which has a length of 3.

Example 2:

Input text1 = "ABC ", text2 =" ABC "output: 3Copy the code

Explanation: The longest common subsequence is “ABC”, which has length 3.

Example 3:

Input: text1 = "ABC ", text2 = "def" output: 0Copy the code

Explanation: Two strings have no common subsequence, return 0.

Tip:

1 <= text1.length, text2.length <= 1000 Text1 and Text2 consist only of lowercase English characters.Copy the code

Answer key

Analysis of the problem solving

Answer:

  1. The longest common subsequence problem is a typical two dimensional dynamic programming problem.
  2. The state transition equation is as follows:
// text1.charAt(i - 1) == text2.charAt(j - 1) dp[i][j] = dp[i - 1][j - 1] + 1; // text1.charAt(i - 1) ! = text2.charAt(j - 1) dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);Copy the code
  1. Final return resultdp[m][n];

Complexity: Time complexity: O(M*N) Space complexity: O(M*N)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :


class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
            // Get the length
            int m = text1.length(), n = text2.length();
            / / create dp
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                char c1 = text1.charAt(i - 1);
                for (int j = 1; j <= n; j++) {
                    char c2 = text2.charAt(j - 1);
                    if (c1 == c2) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); }}}returndp[m][n]; }}Copy the code

Feedback results after submission (because the topic has not been optimized, the performance is mediocre) :

The reference information

  • Force link 1143. Longest common subsequence
  • Dynamic programming