1143. Longest common subsequence

Dynamic programming

Suppose the two strings are respectively

text1 = “abcde”, text2 = “ace” ;

Text1 has length m; Text2 has length n;

Declare a two-dimensional array dp of m*n, as shown below.

text1\text2 a c e
0 0 0 0
a 0
b 0
c 0
d 0
e 0

Matches text1 and text2

Text1 characters are compared to text2 character by character

Dp [I][j] = dp[i-1][j-1]+1;

When the two dimensional array dp [I] [j] string not phase at the same time, dp [I] [j] = Max (dp [j], [I – 1] dp [I] [1])

What does that mean?

Let’s say ‘A’ and ‘ace’

A =1; a =1; j=1; dp[i][j] = dp[0][0]+1;

What does dp[0][0] mean? Dp [0][0] represents the previous common string lengthCopy the code

A =1; C =1; j=2; dp[1][2] = Max(dp[0][2] , dp[1][1]);

Dp [0][2] dp[1][1] In this case, dp[0][2] and dp[1][1] represent the maximum length of the previous public stringCopy the code

Step 1

text1\text2 a c e
0 0 0 0
a 0 1 1 1
b 0
c 0
d 0
e 0

Step 2

text1\text2 a c e
0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0
d 0
e 0

Step 3

text1\text2 a c e
0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0
e 0

Step 4

text1\text2 a c e
0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0

Step 5

text1\text2 a c e
0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3

Text1 = “abcDE “, text2 = “ace”; The longest common substring length is 3;

When text1 = “abcde” and text2 = “ace”, m=5; n=3

From the table above, five sets of graphs appear, each looking for a common substring length for three string group layers;

Therefore, the time complexity of this method is O(Mn). So the space is order MN.