# Java DP Solution (Longest Common Subsequence)

• To make them identical, just find the longest common subsequence. The rest of the characters have to be deleted from the both the strings, which does not belong to longest common subsequence.

``````public int minDistance(String word1, String word2) {
int dp[][] = new int[word1.length()+1][word2.length()+1];
for(int i = 0; i <= word1.length(); i++) {
for(int j = 0; j <= word2.length(); j++) {
if(i == 0 || j == 0) dp[i][j] = 0;
else dp[i][j] = (word1.charAt(i-1) == word2.charAt(j-1)) ? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]);
}
}
int val =  dp[word1.length()][word2.length()];
return word1.length() - val + word2.length() - val;
}``````

• Nice Observation! This is probably the best way to think about it.

• Nice! Your solution could be made simpler by starting `i` and `j` from 1

``````public int minDistance(String word1, String word2) {
int dp[][] = new int[word1.length()+1][word2.length()+1];
for(int i = 1; i <= word1.length(); i++)
for(int j = 1; j <= word2.length(); j++)
dp[i][j] = word1.charAt(i-1) == word2.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
}
``````

• The following coed can be used to visualize the DP matrix to debug.

``````        for(int i = 1; i <= word1.length(); i++){
System.out.print(word1.charAt(i-1));
for(int j = 1; j <= word2.length(); j++){
System.out.print(dp[i][j]);
}
System.out.println();
}
``````

for example, when word 1 = "ear" ,word 2 = "eat".
eat
e111
a122
r122

• C++ Version

``````int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

for(int i = 1; i <= m; i++){
for(int j = 0; j <= n; j++){
dp[i][j] = word1[i-1] == word2[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
}
}

return m + n - 2*dp[m][n];
}``````

• @jaqenhgar I made the same realization. It's a relatively straightforward application of the LCS algorithm (https://en.wikipedia.org/wiki/Longest_common_subsequence_problem). Here's my solution. It beats 90%:

``````public class Solution {
public int minDistance(String word1, String word2) {
int lcs = longestCommonSubsequence(word1, word2);
return (word1.length() - lcs) + (word2.length() - lcs);
}

private int longestCommonSubsequence(String word1, String word2) {
int[][] table = new int[word1.length() + 1][word2.length() + 1];
for (int i = 1; i < table.length; i ++) {
for (int j = 1; j < table[0].length; j ++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
table[i][j] = table[i - 1][j - 1] + 1;
} else {
table[i][j] = Math.max(table[i][j-1], table[i-1][j]);
}
}
}
return table[word1.length()][word2.length()];
}
}
``````

• You only need O(n) space.

int minDistance(string word1, string word2) {

``````    const auto M = word1.size();
const auto N = word2.size();

vector<int> dp(N+1, 0);
for (auto i = 0; i < M; i++) {
auto pre = 0;
for (auto j = 0; j < N; j++) {
const auto tmp = dp[j+1];
dp[j+1] = max(dp[j+1], dp[j]);
if (word1[i] == word2[j]) {
dp[j+1] = max(dp[j+1], pre + 1);
}
pre = tmp;
}
}

return M + N - 2 * dp[N];
}``````

• Use %2 to save space:

``````class Solution {
public:
int minDistance(string word1, string word2) {
int n=word1.length(),m=word2.length();
vector<vector<int>> dp(2,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1[j-1]==word2[i-1])
dp[i%2][j]=dp[(i-1)%2][j-1]+1;
else
dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
}
}
return m+n-2*(dp[m%2][n]);
}
};
``````

• Very smart thinking! but need a lot of practice for the thought to hit your head during an actual interview :D

• @knowledge2thepeople Good point!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.