Edit distance between 2 strings

Question

I have written a program that calculates the "cost" of transforming one string into another. I would like you to review it.

public class EditDistance {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String source="COTI",destination ="CAT";
        System.out.println(getEditDistance(source,destination));
    }

    /**
     * This function finds out the cost of transforming one string to 
     * another
     * any change made to the string costs 1
     * @param sourceString
     * @param destinationString
     * @return
     */
    public static int getEditDistance(String sourceString, String destinationString) {

if (sourceString == null || destinationString == null){
            throw new IllegalArgumentException("String cannot be null");
        }

        int distance = 0;
        int sourceLength = sourceString.length() , destLength = destinationString.length();

        for ( int i=0 ;i < sourceLength && i < destLength ; i++){
            //how can I optimize loop condition, 3 conditions are checked on
            //every iteration
            if (sourceString.charAt(i) != destinationString.charAt(i)){
                //if characters are unequal and increment the distance
                distance++;
            }
        }
        if (destLength !=  sourceLength ){
            distance += Math.abs(sourceLength - destLength);
        }
        return distance;
    }
}

However, I would like to optimize the loop condition. Currently, 3 operations are done.

What can I do to speed it up or make it more elegant?

Answer 1

However, i would like to optimize the loop condition. Currently 3 operations are done. What can I do to speed it up?

Instead of checking for every position if it's within the bounds of both strings, you could save the lowest bound using Math.min and use that as the loop condition. That will cut down one comparison.

Can anyone suggest a more elegant solution?

The last condition checking destLength != sourceLength can be omitted, you can simply add the value of Math.abs because it will give 0 if the lengths are the same. The result will be shorter code, which may be slightly more readable.

To make the code look more elegant, it would be good to follow the common coding style. For example instead of this:

    for ( int i=0 ;i < sourceLength && i < destLength ; i++){

Write like this:

    for (int i = 0; i < sourceLength && i < destLength; i++) {

I use my IDE to correct the formatting. It's a matter of a few key strokes.

It goes without saying that you should remove auto-generated lines like this:

    // TODO Auto-generated method stub

The revised implementation incorporating the above points (and a point from @user1016274 too):

public static int getEditDistance(String sourceString, String destinationString) {
    if (sourceString == null || destinationString == null){
        throw new IllegalArgumentException("String cannot be null");
    }

    int sourceLength = sourceString.length();
    int destLength = destinationString.length();
    int len = Math.min(sourceLength, destLength);

    int distance = Math.abs(sourceLength - destLength);
    for (int i = 0; i < len; ++i) {
        if (sourceString.charAt(i) != destinationString.charAt(i)) {
            ++distance;
        }
    }

    return distance;
}

I would also recommend to add some unit tests to verify the algorithm is working:

@Test
public void test_coti_cat() {
    assertEquals(2, EditDistance.getEditDistance("coti", "cat"));
}

@Test
public void test_alpha_beta() {
    assertEquals(5, EditDistance.getEditDistance("alpha", "beta"));
}

@Test
public void test_beta_pedal() {
    assertEquals(3, EditDistance.getEditDistance("beta", "pedal"));
}

@Test
public void test_empty() {
    assertEquals(3, EditDistance.getEditDistance("", "123"));
}

Answer 2

Though I don't think there's much to optimize with this code, you could terminate the comparison loop at the end of the shorter of the 2 strings:

int distance = Math.abs(sourceLength-destLength)
for ( int i=0 ;i < Math.min(sourceLength, destLength); i++){
...

I am assuming here that there are min() and abs() functions in Java (not my language). Of course you would drop the if statement following the loop then.

Answer 3

Your code fails the test case ["heait", "hit"], edit distance should be 2, but it returns 4. The root of the issue seems to be that you are iterating on both strings sequentially with the same index.
The brute force approach is to use indexOf on the other string.
I heard there's a better solution O(n) with dynamic programming but I haven't seen it yet.