Pacific-Design.com

    
Home Index

1. Algorithms

2. Find 1 Part Distance

Algorithms / Find 1 Part Distance /

Find 1 edit part distance - EditDistance.java

import static java.lang.Math.*;
import java.util.Arrays;

/*
 * bool OnePartDistance(string s1, string s2);
 * return if two words are exactly "one edit" away.

 Examples:
 OnePartDistance("cat", "dog")  = false
 OnePartDistance("cat", "cats") = true    -- insertion
 OnePartDistance("cat", "cut")  = true    -- edit
 OnePartDistance("cat", "cast") = true
 OnePartDistance("cat", "at")   = true    -- removal
 OnePartDistance("cat", "act")  = false
 OnePartDistance("cat", "cat")  = false 

 */
public class EditDistance {

    /*--------------------------------------------------------------------------------------------*/
    public static boolean OnePartDistance(String str1, String str2) {

        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        int width = chars1.length;
        int height = chars2.length;

        int[][] matrix = new int[width + 1][height + 1];

        for (int i = 0; i <= width; i++) {
            matrix[i][0] = i;

            for (int j = 0; j <= height; j++) {
                matrix[0][j] = j;
            }
        }

        displayMatrix(matrix);

        for (int i = 1; i <= width; i++) {

            for (int j = 1; j <= height; j++) {

                // compare characters 
                // if equal, assign current element to diagonal element to complete square
                if (chars1[i - 1] == chars2[j - 1]) {
                    matrix[i][j] = matrix[i - 1][j - 1];
                } 
                else {
                    // find lowest value of current, bottom or right element
                    int lowestNeighbour = min(matrix[i - 1][j - 1] // current element
                                        , (min(matrix[i - 1][j], matrix[i][j - 1])));
                                                // bottom,           right

                    // add lowest values of neighbours + 1 to diagonal elemen to complete square
                    matrix[i][j] = lowestNeighbour + 1;
                }
            }
        }

        displayMatrix(matrix);

        // if matrix last element bottom right is equal to 1, return true
        
        if (matrix[width][height] == 1) {
            return true;
        } else {
            return false;
        }

    }
    /*--------------------------------------------------------------------------------------------*/

    public static void displayMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.printf("%2d", matrix[i][j] );
            }
            System.out.println();
        }
        System.out.println("");
    }
    /*--------------------------------------------------------------------------------------------*/
    public static void line() {
        char[] chars = new char[30];
        Arrays.fill(chars, '-');
        System.out.println(String.valueOf(chars));
    }    
    /*--------------------------------------------------------------------------------------------*/

    public static void main(String[] args) {

        System.out.println("\"cat\" - \"dog\" false=" + OnePartDistance("cat", "dog"));
        line();
        System.out.println("\"cat\" - \"cats\" true=" + OnePartDistance("cat", "cats"));
        line();
        System.out.println("\"cat\" - \"cut\" true=" + OnePartDistance("cat", "cut"));
        line();
        System.out.println("\"cat\", \"cast\" true=" + OnePartDistance("cat", "cast"));
        line();
        System.out.println("\"cat\" - \"at\" true=" + OnePartDistance("cat", "at"));
        line();
        System.out.println("\"cat\" - \"act\" false=" + OnePartDistance("cat", "act"));
        line();
        System.out.println("\"cat\" - \"cat\" false=" + OnePartDistance("cat", "cat"));
    }
    /*--------------------------------------------------------------------------------------------*/

}