EditDistanceDP.java

import java.util.*;

class EditDistance {
  public static int EditDistance(char[] a, char[] b) 
  { 
        // a & b represent two strings.
        // we need to make a DP table to store values
        int [][] editDistanceMemo = new int [a.length + 1][b.length + 1];

        // Initialize all all elements in first row to i representing deletions.
        for (int i = 0; i <= a.length; i++) 
        {
            editDistanceMemo[i][0] = i;
        }

        // Initialize all all elements in first column to j representing insertions.
        for (int j = 0; j <= b.length; j++) 
        {
            editDistanceMemo[0][j] = j;
        }

        // Iterate through each character of a
        for (int i = 1; i <= a.length; i++) 
        {
            // Iterate through each character of b for each element of a.
            for (int j = 1; j <= b.length; j++) 
            {
                // The subproblem is to look at each character of two strings and compare them.
                // Two possibilites exist, they can be equal, they need not be equal.
                if (a[i-1] == b[j-1]) 
                {
                    // if they are equal, then we need not count it towards edit distance.
                    editDistanceMemo[i][j] = editDistanceMemo[i-1][j-1] ;
                }
                else 
                {
                    // If they are not equal, 
                    // then we need to check which of Insert, Replace and Delete generates the lowest edit distance and add 1 to it.
                    // Refer to this youtube.com/watch?v=MiqoA-yF-0M
                    editDistanceMemo[i][j] = 1 + Math.min(Math.min(editDistanceMemo[i-1][j], editDistanceMemo[i][j-1]), editDistanceMemo[i-1][j-1]);
                }
            }
        }
        return editDistanceMemo[a.length][b.length];
  }
  
  public static void main(String args[]) 
  {
    Scanner scan = new Scanner(System.in);

    String s = scan.next();
    String t = scan.next();

    System.out.println(EditDistance(s.toCharArray(), t.toCharArray()));
  }
}