package org.vamsu.interview.solutions.dp;

/**
 * Created by vamsu on 8/2/17.
 */

public class EditDistanceProblem {

    public int editDistanceDP(String s1, String s2) {
        int[][] solution = new int[s1.length() + 1][s2.length() + 1];

        //base case
        //If any of the string if empty then number of operations
        //needed would be equal to the length of other string
        //(Either all characters will be removed or inserted)
        for (int i = 0; i <= s2.length(); i++) {//all elements will be inserted
            solution[0][i] = i;
        }

        for (int i = 0; i <= s1.length(); i++) {//all elements will be removed
            solution[i][0] = i;
        }

        //solving it bottom-up manner
        int m = s1.length();
        int n = s2.length();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //If last characters are matching, ignore the last character
                // then the solution will be same as without the last character.
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    solution[i][j] = solution[i - 1][j - 1];
                else
                    solution[i][j] = 1 + Math.min(solution[i][j - 1], //Insert
                            Math.min(solution[i - 1][j], // Remove
                                    solution[i - 1][j - 1])); //Replace
            }
        }

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.print(solution[i][j]+ "("+ i + "," + j +")  ");
            }
            System.out.println();
        }

        return solution[5][4];
    }

    public static void main(String[] args) {
        String s1 = "vamsi";
        String s2 = "rosy";
        EditDistanceProblem ed = new EditDistanceProblem();
        System.out.println("Minimum Edit Distance -(DP): " + ed.editDistanceDP(s1, s2));
    }
}
