Deletion distance - longest common subsequence

DeletionDistance_longestCommonSubsequence.java

import java.io.*;
import java.util.*;

class Solution {

  static int deletionDistance(String str1, String str2) {
    int len1 = str1.length(), len2 = str2.length();
    int[][] dp = new int[len1 + 1][len2 + 1];
    
    for (int i = 1; i <= len1; i++) {
      for (int j = 1; j <= len2; j++) {
        if (str1.charAt(i - 1) == str2.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 len1 + len2 - 2 * dp[len1][len2];
  }

  public static void main(String[] args) {
  }
}

//dp[i][j]
// i the first i chars of str1
// j the first j chars of str2
// dp[i][j]  
// len(str1) + len(str2) - 2 * dp[len(str1)][len(str2)]
// str1
// str2

//og  
//go

//doag
//frobg

//og
//og

//
//do
//fro

//d   + 1
//fr  + 1

//d
//fro 

//do
//fr