# Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example

For `"ABCD"` and `"EDCA"`, the LCS is `"A"` (or `"D"`, `"C"`), return `1`.

For `"ABCD"` and `"EACB"`, the LCS is `"AC"`, return `2`.

Clarification

What’s the definition of Longest Common Subsequence?

Solution: Dynamic Programming

```public int longestCommonSubsequence(String A, String B) {
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return 0;
}
int[][] lcs = new int[A.length()][B.length()];
for (int i = 0; i < A.length(); i++) {
for (int j = 0; j < B.length(); j++) {
if (i == 0 || j == 0) {
lcs[i][j] = A.charAt(i) == B.charAt(j) ? 1 : 0;
} else {
if (A.charAt(i) == B.charAt(j)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}
}
return lcs[A.length() - 1][B.length() - 1];
}```
Share

# Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Example
Given A = “ABCD”, B = “CBCE”, return 2.

Note
The characters in substring should occur continuously in original string. This is different with subsequence.

Challenge
O(n x m) time and memory.

Solution: Dynamic Programming

```public int longestCommonSubstring(String A, String B) {
int[][] lcs = new int[A.length()][B.length()];
int max = 0;
for (int i = 0; i < A.length(); i++) {
for (int j = 0; j < B.length(); j++) {
if (A.charAt(i) == B.charAt(j)) {
if (i == 0 || j == 0) {
lcs[i][j] = 1;
} else {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
}
}
if (lcs[i][j] > max) {
max = lcs[i][j];
}
}
}
return max;
}```

# Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

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

Given S = `"rabbbit"`, T = `"rabbit"`, return `3`.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

Solution: Dynamic Programming

Version 1. O(m*n)time O(m*n)space
f[i][j] means the number of different ways to select first j chars of T from first i chars from S, 即从S的前i个字符中挑出T的前j个字符 有多少种方案
f[i][j] = f[i-1][j-1] + f[i-1][j] //S[i]=T[j]
= f[i-1][j] //S[i]!=T[j]

```public int numDistinct(String S, String T) {
//f[i][j] means the number of different ways to select first j chars of T from first i chars from S
//从S的前i个字符中挑出T的前j个字符 有多少种方案
//f[i][j] = f[i-1][j-1] + f[i-1][j] //S[i]=T[j]
//      = f[i-1][j] //S[i]!=T[j]
if (S == null || T == null || S.length() < T.length()) {
return 0;
}
int[][] numDistinct = new int[S.length() + 1][T.length() + 1];
for (int i = 0; i <= S.length(); i++) {
numDistinct[i][0] = 1;
}
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= i && j <= T.length(); j++) {
if (S.charAt(i - 1) == T.charAt(j - 1)) {
numDistinct[i][j] = numDistinct[i - 1][j - 1] + numDistinct[i - 1][j];
} else {
numDistinct[i][j] = numDistinct[i - 1][j];
}
}
}
return numDistinct[S.length()][T.length()];
}```

Version 2. O(m*n) time, O(n)space

just mod 2 for the row index. Rolling array.

```public int numDistinct(String S, String T) {
if (S == null || T == null || S.length() < T.length()) {
return 0;
}
int[][] numDistinct = new int[2][T.length() + 1];
for (int i = 0; i < 2; i++) {
numDistinct[i][0] = 1;
}
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= i && j <= T.length(); j++) {
if (S.charAt(i - 1) == T.charAt(j - 1)) {
numDistinct[i % 2][j] = numDistinct[(i - 1) % 2][j - 1] + numDistinct[(i - 1) % 2][j];
} else {
numDistinct[i % 2][j] = numDistinct[(i - 1) % 2][j];
}
}
}
return numDistinct[S.length() % 2][T.length()];
}```

# Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (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

Given word1 = `"mart"` and word2 = `"karma"`, return `3`.

Solution: Dynamic Programming

f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b[j]

= MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j]

intialize: f[i][0] = i, f[0][j] = j

```public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return -1;
}
//minDistance[i][j] = minimum distance to convert first i chars of word 1
//to first j chars of word 2
int[][] minDistance = new int[word1.length() + 1][word2.length() + 1];
//init the first column -- word2 is empty
for (int i = 0; i < minDistance.length; i++) {
minDistance[i][0] = i;
}
//init the first row -- word1 is empty
for (int j = 0; j < minDistance[0].length; j++) {
minDistance[0][j] = j;
}

for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
minDistance[i][j] = Math.min(Math.min(minDistance[i - 1][j - 1],
minDistance[i - 1][j] + 1), minDistance[i][j - 1] + 1);
} else {
minDistance[i][j] = Math.min(Math.min(minDistance[i - 1][j - 1],
minDistance[i - 1][j]), minDistance[i][j - 1]) + 1;
}
}
}
return minDistance[word1.length()][word2.length()];
}```