@@ -0,0 +1,1750 @@
+package com.vaibhavsahu.interviews;%0A%0A/*%0A*Author: Vaibhav Sahu%0A* Topic: Dynamic Programming%0A* Problem: Edit Distance%0A* */%0A%0A%0Apublic class Main %7B%0A%0A    public static int minEditDistance(String s1, String s2)%7B%0A        //public static int minDistance(String s1, String s2) %7B%0A            int l1 = s1.length();%0A            int l2 = s2.length();%0A%0A            // len1+1, len2+1, because finally return dp%5Blen1%5D%5Blen2%5D%0A            int%5B%5D%5B%5D length = new int%5Bl1 + 1%5D%5Bl2 + 1%5D;%0A%0A            for (int i = 0; i %3C= l1; i++) %7B%0A                length%5Bi%5D%5B0%5D = i;%0A            %7D%0A%0A            for (int j = 0; j %3C= l2; j++) %7B%0A                length%5B0%5D%5Bj%5D = j;%0A            %7D%0A%0A            //iterate though, and check last char%0A            for (int i = 0; i %3C l1; i++) %7B%0A                char c1 = s1.charAt(i);%0A                for (int j = 0; j %3C l2; j++) %7B%0A                    char c2 = s2.charAt(j);%0A%0A                    //if last two chars equal%0A                    if (c1 == c2) %7B%0A                        //update dp value for +1 length%0A                        length%5Bi + 1%5D%5Bj + 1%5D = length%5Bi%5D%5Bj%5D;%0A                    %7D else %7B%0A                        int replace = length%5Bi%5D%5Bj%5D + 1;%0A                        int insert = length%5Bi%5D%5Bj + 1%5D + 1;%0A                        int delete = length%5Bi + 1%5D%5Bj%5D + 1;%0A%0A                        int min = replace %3E insert ? insert : replace;%0A                        min = delete %3E min ? min : delete;%0A                        length%5Bi + 1%5D%5Bj + 1%5D = min;%0A                    %7D%0A                %7D%0A            %7D%0A%0A            return length%5Bl1%5D%5Bl2%5D;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A%09// write your code here%0A        String s1 = %22sunday%22;%0A        String s2 = %22saturday%22;%0A%0A        System.out.println(minEditDistance(s1, s2));%0A%0A    %7D%0A%7D%0A

Edit Distance