uopspop

Untitled

Oct 5th, 2019
168
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×