# 1223. Algorithm - Two Sequences DPDP

Introduce dynamic programming.

## 4. Two Sequences DP

### 4.1 Longest Common Subsequence

#### 4.1.1 Problem Description

Given two strings, find the longest common subsequence (LCS). Your code should return the length of LCS.

Example 1:
Input:  "ABCD" and "EDCA"
Output:  1
Explanation: LCS is 'A' or  'D' or 'C'.
Example 2:
Input: "ABCD" and "EACB"
Output:  2
Explanation: LCS is "AC"


#### 4.1.2 DP Solution(n^2)

// O(n^2)
public int longestCommonSubsequence(String A, String B) {
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return 0;
}

int m = A.length();
int n = B.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}

return dp[m][n];
}

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n^2)$

### 4.2 Uncrossed Lines

#### 4.2.1 Problem Description

We write the integers of A and B (in the order they are given) on two separate horizontal lines. Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:

• A[i] == B[j];
• The line we draw does not intersect any other connecting (non-horizontal) line.
• Each number can only belong to one connecting line.

Return the maximum number of connecting lines we can draw in this way.

Example 1:
Input: A = [1,4,2], B = [1,2,4]
Output:  2
Explanation: We can draw line from A=1 to B=1 and line from A=4 to B=4. We cannot draw line
from A=4 to B=4 and line from A=2 to B=2 at the same time because they intersect each other.
Example 2:
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3
Explanation: One solution is A=2 -> B=2, A=5 to B=5 and A=2 to B=2
Example 3:
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2
Explanation: One solution is A=1 -> B=1 and A=1 to B=1


#### 4.2.2 DP Solution(n^2)

This question is exactly same with Longest Common Sequence.

// same as longest common subsequence, O(n^2)
public int maxUncrossedLines(int[] A, int[] B) {
int m = A.length;
int n = B.length;

int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}

return dp[m][n];
}

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n^2)$

### 4.3 Minimum Edit Distance

#### 4.3.1 Problem Description

Given two strings A and B, find the minimum number of steps required to convert A to B. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character
Example 1:
Input: A="horse", B="ros"
Output:  3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: A="intention", B="execution"
Output:  5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')


#### 4.3.2 DP Solution(n^2)

// O(n^2)
public int minDistance(String A, String B) {
int m = A.length();
int n = B.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {
dp[i] = i;
}
for (int j = 1; j <= n; j++) {
dp[j] = j;
}

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 1) dp[i][j - 1], insert character at end of A
// 2) dp[i - 1][j], delete A's last character
// 3) dp[i - 1][j - 1], replace A's last character
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}

return dp[m][n];
}

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n^2)$

### 4.4 Distinct Subsequences

#### 4.4.1 Problem Description

Given two strings S and T. Count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not)

Example 1:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation: You could remove any 'b' in S, so there are 3 ways to get T.

Example 2:
Input: S = "abcd", T = ""
Output: 1
Explanation: There is only 1 way to get T - remove all chars in S.


#### 4.4.2 DP Solution(n^2)

// O(n^2)
public int numDistinct(String S, String T) {
int m = S.length();
int n = T.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 0; i <= m; i++) {
dp[i] = 1;
}

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (S.charAt(i - 1) == T.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // case 1: last character in T is same with that in S
}
dp[i][j] += dp[i-1][j]; // case 2: last character in T is not same with that in S
}
}

return dp[m][n];
}

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n^2)$

### 4.5 Interleaving String

#### 4.5.1 Problem Description

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:
Input: s1 = "", s2 = "", s3 = "1"
Output: false

Example 3:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false


#### 4.5.2 DP Solution(n^2)

// O(n^2)
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();

if (m + n != s3.length()) {
return false;
}

boolean[][] dp = new boolean[m+1][n+1];
dp = true;
for (int i = 1; i <= m; i++) {
if (s1.charAt(i-1) == s3.charAt(i-1)) {
dp[i] = true;
} else {
break;
}
}
for (int j = 1; j <= n; j++) {
if (s2.charAt(j-1) == s3.charAt(j-1)) {
dp[j] = true;
} else {
break;
}
}

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s3.charAt(i+j-1)) {
dp[i][j] = dp[i][j] || dp[i-1][j];
}
if (s2.charAt(j - 1) == s3.charAt(i+j-1)) {
dp[i][j] = dp[i][j] || dp[i][j-1];
}
}
}

return dp[m][n];
}

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n^2)$