Find hamming distance between two Strings of equal length in Java

Question

I have a private class that I want to be able to find the shortest Hamming Distance between two Strings of equal length in Java. The private class holds a char[] and contains a method to compare against other char arrays. It returns true if there is only a hamming distance of one.

The average length of the Strings used is 9 characters. They range from 1 to 24 characters.

Is there a way to make the isDistanceOne(char[]) method go any faster?

private class WordArray {

  char[] word;

  /**
   * Creates a new WordArray object.
   *
   * @param word The word to add to the WordArray.
   */
  private WordArray(String word) {
     this.word = word.toCharArray();
  }

  /**
   * Returns whether the argument is within a Hamming Distance of one from
   * the char[] contained in the WordArray.
   *
   * Both char[]s should be of the same length.
   *
   * @param otherWord The word to compare with this.word.
   * @return boolean.
   */
  private boolean isDistanceOne(char[] otherWord) {

     int count = 0;

     for(int i = 0; i < otherWord.length; i++) {
        if (this.word[i] != otherWord[i])
           count++;
     }

     return (count == 1);
  }
}

Answer 1

Given the limited context, and no information about where the hotspot is in the code, it's difficult to give concrete advice. Here are some musings for your consideration:

For ease of reading, it's preferable to have whitespace after control flow keywords and before the (.

It is suggested to always include curly braces, even when they're not required by the compiler.

Use final where possible to reduce cognitive load on the readers of your code.

word should be private.

There's no apparent reason to use char[] instead of just keeping a pointer to the original String. They're costing you time and space to make, to no benefit.

You can short-circuit out of your for loop if the count ever becomes greater than one. Unless a significant fraction of your inputs have a distance of one, you should see some performance gain here.

Using a boolean instead of an int might make a very small difference in execution time, but that would need to be tested. It also makes the code harder to read.

private class WordArray {

    private final String word;

    private WordArray(final String word) {
        this.word = word;
    }

    private boolean isDistanceOne(final char[] otherWord) {
        assert word.length() == otherWord.length;

        int distance = 0;

        for (int i = 0; i < otherWord.length; i++) {
            if (this.word.charAt(i) == otherWord[i]) {
                continue;
            }

            if (distance > 0) {
                return false;
            }

            distance++;
        }


        return distance == 1;
    }
}

Answer 2

I don't think you can beat that linear complexity since you need to look at each character to determine the Hamming distance.

One small optimization you can do is to short-circuit once your count goes above one, but that adds an extra check in every iteration, so it might have worse runtime depending on the inputs.