Advertisement
uopspop

Untitled

Oct 5th, 2019
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.10 KB | None | 0 0
  1. import java.awt.*;
  2. import java.util.Stack;
  3.  
  4. public class DP_Edit_Distance {
  5.  
  6.     public static void main(String[] args) {
  7.  
  8.         String str1 = "EXPONENTIAL";
  9.         String str2 = "POLYNOMIAL";
  10.  
  11.         Integer cost = dp_edit_distance(str1, str2);
  12.         System.out.println("result:" + cost);
  13.         System.out.println();
  14.     }
  15.  
  16.     private static int dp_edit_distance(String str1, String str2) {
  17.         int cost = 0; // the number of columns in which the letters differ
  18.         int numOfRow = str1.length()+1; // the index represents the number of char used in the string this time
  19.         int numOfCol = str2.length()+1;
  20.  
  21.         int[][] costMap = new int[numOfRow][numOfCol]; // to record the current best cost in each run
  22.         int[][] parent_row = new int[numOfRow][numOfCol]; // to mark the final path for each destination
  23.         int[][] parent_col = new int[numOfRow][numOfCol]; // to mark the final path for each destination
  24.  
  25.         // initialize the costMap
  26.         for (int i = 0; i < costMap.length; i++) {
  27.             for (int j = 0; j < costMap[i].length; j++) {
  28. //                costMap[i][j] = Integer.MAX_VALUE;
  29.                 costMap[i][j] = -1;
  30.             }
  31.         }
  32.  
  33.         // set up the base case
  34.         for (int i = 0; i < numOfRow; i++) { // do not use 0
  35.             costMap[i][0] = i;
  36.             parent_row[i][0] = i-1;
  37.             parent_col[i][0] = 0;
  38.         }
  39.         for (int j = 0; j < numOfCol; j++) { // do not use 0
  40.             costMap[0][j] = j;
  41.             parent_row[0][j] = 0;
  42.             parent_col[0][j] = j-1;
  43.         }
  44.  
  45.         System.out.println("base state: ");
  46.         print2DArray(costMap);
  47.  
  48.         // bottom up
  49.         for (int i = 1; i < numOfRow; i++) {
  50.             for (int j = 1; j < numOfCol; j++) {
  51.  
  52.                 int costOfstr1InTheRightestSide = 1 + costMap[i-1][j];
  53.                 int costOfstr2InTheRightestSide = 1 + costMap[i][j-1];
  54.                 int costOfstr12InTheSameRightestSide = costMap[i-1][j-1];
  55.                 if (str1.charAt(i-1) != str2.charAt(j-1)) costOfstr12InTheSameRightestSide += 1; // attention: string is 1 less in terms of length with costMap
  56.  
  57.                 // find the min
  58.                 int min = 0;
  59.                 if (costOfstr1InTheRightestSide <= costOfstr2InTheRightestSide &&  costOfstr1InTheRightestSide < costOfstr12InTheSameRightestSide) {
  60.                     min = costOfstr1InTheRightestSide;
  61.                     parent_row[i][j] = i-1;
  62.                     parent_col[i][j] = j;
  63.                 } else if (costOfstr2InTheRightestSide <= costOfstr1InTheRightestSide && costOfstr2InTheRightestSide <= costOfstr12InTheSameRightestSide) {
  64.                     min = costOfstr2InTheRightestSide;
  65.                     parent_row[i][j] = i;
  66.                     parent_col[i][j] = j-1;
  67.                 } else if (costOfstr12InTheSameRightestSide <= costOfstr1InTheRightestSide && costOfstr12InTheSameRightestSide <= costOfstr12InTheSameRightestSide) {
  68.                     min = costOfstr12InTheSameRightestSide;
  69.                     parent_row[i][j] = i-1;
  70.                     parent_col[i][j] = j-1;
  71.                 }
  72.  
  73.                 costMap[i][j] = min;
  74.             } // end of inner for
  75.         } // end of outer for
  76.  
  77.         System.out.println("end state: ");
  78.         print2DArray(costMap);
  79.  
  80.         System.out.println("end parent - row: ");
  81.         print2DArray(parent_row);
  82.         System.out.println("end parent - col: ");
  83.         print2DArray(parent_col);
  84.  
  85.         cost = costMap[numOfRow-1][numOfCol-1];
  86.  
  87.         // visualize the final
  88.         System.out.printf("final route to the destination: (%d,%d)%n", numOfRow-1, numOfCol-1);
  89.         visualizeTheFinal(numOfRow-1, numOfCol-1, parent_row, parent_col);
  90. //        visualizeTheFinal(7, 5, parent_row, parent_col);
  91.  
  92.         return cost;
  93.     }
  94.  
  95.     private static void visualizeTheFinal(int numOfRow, int numOfCol, int[][] parent_row, int[][] parent_col) {
  96.  
  97.         Stack<String> stack = new Stack<String>();
  98.  
  99.         int current_parent_row = numOfRow;
  100.         int current_parent_col = numOfCol;
  101.         stack.push("("+ current_parent_row  + "," + current_parent_col + ")");
  102. //        System.out.printf("(%d,%d)%n", current_parent_row, current_parent_col);
  103.         while(true){
  104.             current_parent_row = parent_row[current_parent_row][current_parent_col];
  105.             current_parent_col = parent_col[current_parent_row][current_parent_col];
  106.  
  107.             if (current_parent_row < 0 || current_parent_col < 0) break;
  108.  
  109.             stack.push("("+ current_parent_row  + "," + current_parent_col + ")");
  110. //            System.out.printf("(%d,%d)%n", current_parent_row, current_parent_col);
  111.  
  112.         }
  113.  
  114.         // print
  115.         while (!stack.isEmpty()){
  116.             System.out.printf("%s <- ", stack.pop());
  117.         }
  118.         System.out.println();
  119.  
  120.  
  121.     }
  122.  
  123.     private static void print2DArray(int[][] ary){
  124.         for (int i = 0; i < ary.length; i++) {
  125.             for (int j = 0; j < ary[i].length; j++) {
  126.                 System.out.printf("%3d" , ary[i][j]);
  127.             }
  128.             System.out.println();
  129.         }
  130.     }
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement