I don’t know who you are when you put your clothes on? Let’s talk about the longest ascending subsequence, which has been well received. Today we are going to show you the longest common subsequence series.
The longest common subsequence is a classic algorithm problem. Some will just tell you to find the longest ascending subsequence, some will say it differently, but you’re still looking at the longest common subsequence. So the question is, can you still see it with its clothes on?
If you can’t see it at all, you’re not ready for abstract thinking. Those of you who read my problems often know that I always emphasize abstract thinking. Without abstract thinking, all questions are new to you. You can’t transfer your previous experience to this problem, so what’s the point of your problem?
Although abstract thinking is difficult to practice, but fortunately, the algorithm is limited, often examined question type is limited. Starting with these things might make your life a little easier. This article will help you further understand abstract thinking from a classic to impossible question “the longest common subsequence”.
❝
Pay attention to. The purpose of this paper is to help you identify the routine and clarify the thinking frame of solving the problem from the horizontal perspective. The optimal solution is not adopted. All the solutions given by the problem may not be optimal, but they can pass all the test cases. If you want to see the best solution, you can just go to the discussion section. Or look forward to my in-depth analysis series.
❞
718. Longest repeating subarray
Title address
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
Topic describes
Given two integer arrays A and B, return the length of the longest common subarray of the two arrays.
Example 1:
Input:A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3Explanation:The longest common subarray is [3, 2, 1].Description: 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100 Copy the codeFront knowledge
- Hash table
- An array of
- Binary search
- Dynamic programming
Train of thought
This is the classic longest common subsequence problem. In general, dynamic programming can be considered for solving the problem of “maximizing or minimizing two arrays or strings”, and dp[I][j] is usually defined as XXX ending with A[I], B[j]. The length of the longest common subarray of two arrays ending with A[I], B[j].
❝
The choice of state transition equations can be referred to as: I don’t know you with clothes on? Let’s talk about the longest ascending subsequence
❞
The algorithm is simple:
- Double loop to find all combinations of I and j, time complexity
, where m and n are the lengths of A and B respectively.
- If A[I] == B[j], dp[I][j] = DP [i-1][J-1] + 1
- Otherwise, dp[I][j] = 0
- The maximum value can be recorded in the loop process.
“Remember this state transition equation, which we’re going to use a lot.“
Key point resolution
- Dp modeling routine
code
Code support: Python
Python Code:
class Solution:
def findLength(self, A, B):
m, n = len(A), len(B)
ans = 0
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1) : for j in range(1, n + 1) : if A[i - 1] == B[j - 1] : dp[i][j] = dp[i - 1][j - 1] + 1 ans = max(ans, dp[i][j]) return ans Copy the code“Complexity analysis“
- Time complexity:, where m and n are the lengths of A and B respectively.
- Space complexity:, where M and n are the lengths of A and B respectively.
❝
Binary search is also possible, but it’s not easy to think of, so you can try it.
❞
1143. Longest common subsequence
Title address
https://leetcode-cn.com/problems/longest-common-subsequence
Topic describes
Given two strings text1 and text2, return the length of the longest common subsequence of the two strings.
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.
Returns 0 if the two strings have no common subsequence.
Example 1:
Input: text1 = “abcde”, text2 = “ace” Output: 3 Explanation: The longest common subsequence is “ace”, which has length 3. Example 2:
Input: text1 = “ABC “, text2 =” ABC “Output: 3 Explanation: The longest common subsequence is” ABC “, which has length 3. Example 3:
Input: text1 = “ABC “, text2 = “def” Output: 0 Explanation: The two strings have no common subsequence, return 0.
Tip:
1 <= text1.length <= 1000 1 <= text2.length <= 1000 The entered character string contains only lowercase English characters.
Front knowledge
- An array of
- Dynamic programming
Train of thought
Similar to the above problem, except that arrays become strings (which doesn’t matter) and subarrays (continuous) become subsequences (discontinuous).
The algorithm requires only A small tweak: if A[I]! = B [j], then the dp [I] [j] = Max (dp [j], [I – 1] dp [I] [1])
Key point resolution
- Dp modeling routine
code
❝
You can see how the code looks
❞
Code support: Python
Python Code:
class Solution:
def longestCommonSubsequence(self, A: str, B: str) -> int:
m, n = len(A), len(B)
ans = 0
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1) : for j in range(1, n + 1) : if A[i - 1] == B[j - 1] : dp[i][j] = dp[i - 1][j - 1] + 1 ans = max(ans, dp[i][j]) else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return ans Copy the code“Complexity analysis“
- Time complexity:, where m and n are the lengths of A and B respectively.
- Space complexity:, where M and n are the lengths of A and B respectively.
1035. Intersecting lines
Title address
https://leetcode-cn.com/problems/uncrossed-lines/description/
Topic describes
We write down the integers in A and B in A given order on two separate horizontal lines.
Now we can draw some lines connecting two numbers A[I] and B[j], as long as A[I] == B[j] and the line we draw does not intersect any other line (non-horizontal).
Draw lines in this way and return the maximum number of lines we can draw.
Example 1:
Input: A = [1,4,2], B = [1,2,4] output: 2 explanation: we can draw two lines that do not cross, as shown in the figure above. We cannot draw A third line that does not intersect because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2. Example 2:
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1] output: 2
Tip:
1 <= A.length <= 500 1 <= B.length <= 500 1 <= A[i], B[i] <= 2000
Front knowledge
- An array of
- Dynamic programming
Train of thought
As can be seen from the figure, if we want to avoid intersection, the relative position must be consistent, in other words: “common subsequence”. Therefore, it is the same as 1143. Longest common subsequence, and the code is exactly the same.
Key point resolution
- Dp modeling routine
code
❝
You can see how the code looks
❞
Code support: Python
Python Code:
class Solution:
def longestCommonSubsequence(self, A: str, B: str) -> int:
m, n = len(A), len(B)
ans = 0
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1) : for j in range(1, n + 1) : if A[i - 1] == B[j - 1] : dp[i][j] = dp[i - 1][j - 1] + 1 ans = max(ans, dp[i][j]) else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return ans Copy the code“Complexity analysis“
- Time complexity:, where m and n are the lengths of A and B respectively.
- Space complexity:, where M and n are the lengths of A and B respectively.
conclusion
The first question is “subsequence” type, the second and third questions are “subsequence”. The state definition is the same whether it is a “substring” or a “subsequence”, with only a minor difference.
“You have to master basic data structures and algorithms to handle complex problems.” Basic algorithm, it thoroughly understand, and then to face a variety of people change skin is not afraid. On the other hand, if you don’t think about the logic behind the question, it will be painful. You won’t be able to do it if the topic changes a little bit, which is one of the reasons why many people say that they “brush a lot of questions, but they still can’t do new questions”. Pay attention to the public number force buckle plus, and strive to use clear and straightforward language restore problem solving ideas, and there are a lot of diagrams, hand in hand to teach you to identify routines, efficient brush.
More antithesis can access my LeetCode antithesis warehouse: https://github.com/azl397985856/leetcode. It currently has 30K star.
