“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
[topic address]
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 formed by deleting some characters (or none) from the original string without changing the relative order of the characters.
- For example,
"ace"是"abcde"Of, but"aec"not"abcde"Subsequence of.
A common subsequence of two strings is a subsequence that is shared by both strings.
Example 1:
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace", which has length 3.Copy the codeExample 2:
Input: text1 = "ABC ", text2 =" ABC "Output: 3 Explanation: The longest common subsequence is" ABC ", which has length 3.Copy the codeExample 3:
Input: text1 = "ABC ", text2 = "def" Output: 0 Explanation: The two strings have no common subsequence, return 0.Copy the codeTip:
1 <= text1.length, text2.length <= 1000text1和text2Contains only lowercase English characters.
The problem needs to solve the longest common subsequence of two strings, involving the problem of finding the optimal solution, we can solve the problem through dynamic programming
State definition
So let’s first think about the question, what does the longest common subsequence of this problem have to do with?
The answer is given the length of two strings, so the state definition in this case is a two-dimensional DP
Dp [I][j] => the length of the longest common subsequence of text1[I] text2[j] position
Transfer equation
The state transition equation in this case needs to be discussed separately
text1[i]! ==text2[j]
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
text1[i]===text2[j]
dp[i][j] = dp[i-1][j-1]+1
At this point, the problem is solved
The first version of the code is as follows:
Var longestCommonSubsequence = function(text1, text2) {const len1 = text1.length, len2 = text2.length, const len2 = text2.length, Dp = [[]] for(let j = 0; j<=len2; j++){ dp[0][j] = 0; } // Find the longest common subsequence length of each subsequence for(let I = 1; i<=len1; i++){ dp[i] = [0]; for(let j = 1; j<=len2; j++){ if(text1[i-1]===text2[j-1]){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]) } } } return dp[len1][len2] };Copy the codeNote: we used a trick to store the value of subscript I at the location of subscript I +1. This is because when I =0, I -1 does not exist
After the above code was submitted, it beat around 90% of users in time, but only 7% of users in memory consumption
So how should we optimize the spatial complexity of the above problems?
Here we can use the scrolling array technique to optimize the spatial complexity of the above problems
According to the transfer equation, when we update the data of dp[I], we only rely on the value of dp[i-1], so our DP array only needs to maintain dp[0] dp[1], the specific method is as follows:
We store the value of the current row at the index of I %2, and then use the current index for the previous row! cur*1
If I take 1, I get 1, and then I get! Cur *1 is 0 if you take 2 for example, you get 0! Cur * 1 get 1
The second version of the code is as follows:
Var longestCommonSubsequence = function(text1, text2) {const len1 = text1.length, len2 = text2.length, const len2 = text2.length, Dp = [[],[]] for(let j = 0; j<=len2; j++){ dp[0][j] = 0; dp[1][j] = 0; } // Find the longest common subsequence length for each position for(let I = 1; i<=len1; i++){ let cur = i%2, pre = ! cur*1; for(let j = 1; j<=len2; j++){ if(text1[i-1]===text2[j-1]){ dp[cur][j] = dp[pre][j-1]+1; }else{ dp[cur][j] = Math.max(dp[cur][j-1],dp[pre][j]) } } } return dp[len1%2][len2] };Copy the codeAfter the above code is submitted, beat 90+% users in time and beat 90+% users in memory consumption
At this point we are done with leetcode- Finger Offer II 095- longest common subsequence
If you have any questions or suggestions, please leave a comment!