Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.awt.*;
- import java.util.Stack;
- public class DP_Edit_Distance {
- public static void main(String[] args) {
- String str1 = "EXPONENTIAL";
- String str2 = "POLYNOMIAL";
- Integer cost = dp_edit_distance(str1, str2);
- System.out.println("result:" + cost);
- System.out.println();
- }
- private static int dp_edit_distance(String str1, String str2) {
- int cost = 0; // the number of columns in which the letters differ
- int numOfRow = str1.length()+1; // the index represents the number of char used in the string this time
- int numOfCol = str2.length()+1;
- int[][] costMap = new int[numOfRow][numOfCol]; // to record the current best cost in each run
- int[][] parent_row = new int[numOfRow][numOfCol]; // to mark the final path for each destination
- int[][] parent_col = new int[numOfRow][numOfCol]; // to mark the final path for each destination
- // initialize the costMap
- for (int i = 0; i < costMap.length; i++) {
- for (int j = 0; j < costMap[i].length; j++) {
- // costMap[i][j] = Integer.MAX_VALUE;
- costMap[i][j] = -1;
- }
- }
- // set up the base case
- for (int i = 0; i < numOfRow; i++) { // do not use 0
- costMap[i][0] = i;
- parent_row[i][0] = i-1;
- parent_col[i][0] = 0;
- }
- for (int j = 0; j < numOfCol; j++) { // do not use 0
- costMap[0][j] = j;
- parent_row[0][j] = 0;
- parent_col[0][j] = j-1;
- }
- System.out.println("base state: ");
- print2DArray(costMap);
- // bottom up
- for (int i = 1; i < numOfRow; i++) {
- for (int j = 1; j < numOfCol; j++) {
- int costOfstr1InTheRightestSide = 1 + costMap[i-1][j];
- int costOfstr2InTheRightestSide = 1 + costMap[i][j-1];
- int costOfstr12InTheSameRightestSide = costMap[i-1][j-1];
- if (str1.charAt(i-1) != str2.charAt(j-1)) costOfstr12InTheSameRightestSide += 1; // attention: string is 1 less in terms of length with costMap
- // find the min
- int min = 0;
- if (costOfstr1InTheRightestSide <= costOfstr2InTheRightestSide && costOfstr1InTheRightestSide < costOfstr12InTheSameRightestSide) {
- min = costOfstr1InTheRightestSide;
- parent_row[i][j] = i-1;
- parent_col[i][j] = j;
- } else if (costOfstr2InTheRightestSide <= costOfstr1InTheRightestSide && costOfstr2InTheRightestSide <= costOfstr12InTheSameRightestSide) {
- min = costOfstr2InTheRightestSide;
- parent_row[i][j] = i;
- parent_col[i][j] = j-1;
- } else if (costOfstr12InTheSameRightestSide <= costOfstr1InTheRightestSide && costOfstr12InTheSameRightestSide <= costOfstr12InTheSameRightestSide) {
- min = costOfstr12InTheSameRightestSide;
- parent_row[i][j] = i-1;
- parent_col[i][j] = j-1;
- }
- costMap[i][j] = min;
- } // end of inner for
- } // end of outer for
- System.out.println("end state: ");
- print2DArray(costMap);
- System.out.println("end parent - row: ");
- print2DArray(parent_row);
- System.out.println("end parent - col: ");
- print2DArray(parent_col);
- cost = costMap[numOfRow-1][numOfCol-1];
- // visualize the final
- System.out.printf("final route to the destination: (%d,%d)%n", numOfRow-1, numOfCol-1);
- visualizeTheFinal(numOfRow-1, numOfCol-1, parent_row, parent_col);
- // visualizeTheFinal(7, 5, parent_row, parent_col);
- return cost;
- }
- private static void visualizeTheFinal(int numOfRow, int numOfCol, int[][] parent_row, int[][] parent_col) {
- Stack<String> stack = new Stack<String>();
- int current_parent_row = numOfRow;
- int current_parent_col = numOfCol;
- stack.push("("+ current_parent_row + "," + current_parent_col + ")");
- // System.out.printf("(%d,%d)%n", current_parent_row, current_parent_col);
- while(true){
- current_parent_row = parent_row[current_parent_row][current_parent_col];
- current_parent_col = parent_col[current_parent_row][current_parent_col];
- if (current_parent_row < 0 || current_parent_col < 0) break;
- stack.push("("+ current_parent_row + "," + current_parent_col + ")");
- // System.out.printf("(%d,%d)%n", current_parent_row, current_parent_col);
- }
- // print
- while (!stack.isEmpty()){
- System.out.printf("%s <- ", stack.pop());
- }
- System.out.println();
- }
- private static void print2DArray(int[][] ary){
- for (int i = 0; i < ary.length; i++) {
- for (int j = 0; j < ary[i].length; j++) {
- System.out.printf("%3d" , ary[i][j]);
- }
- System.out.println();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement