2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Is it an implementation of the Levenshtein distance algorithm or did you do it from scratch ? \$\endgroup\$ – Loufylouf Mar 9 '15 at 16:24
  • \$\begingroup\$ I do not know what is 'Levenshtein distance algorithm'. Yes, I have implemented this from scratch \$\endgroup\$ – Aneesh K Mar 9 '15 at 16:25
  • 1
    \$\begingroup\$ A more interesting problem would be to consider additions and deletions as single edits. So that the string "word" and the string "sword" have a distance of 1 instead of 5. I believe this is what Loufylouf is referring to as "Levenshtein distance". \$\endgroup\$ – JS1 Mar 10 '15 at 6:00
3
\$\begingroup\$

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"));
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ To further improve on your good answer - I would add a separate guard statement for sourceString and destinationString being null. Getting an IllegalArgumentException that doesn't specify which of the arguments was null is less debugging-friendly. I'd also be inclined improve on the naming - eg. shorterLength instead of len. \$\endgroup\$ – Konrad Morawski Mar 7 '19 at 13:47
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.