Java match string with x allowed mismatches.

Question

What is the fastest / clearest way to see if a string matches to another string of the same length with X allowed mismatches? Is there a library that can do this, its not in Apache stringUtils (there is only one that also uses insertions / deletions).

So lets say I have 2 string of length for and I want to know if they match with 1 mismatch allowed. Insertions and deletions are not allowed.

So:

ABCD <-> ABCD = Match

ABCC <-> ABCD = Match with 1 mismatch

ACCC <-> ABCD = no match, 2 mismatches is too much.

Answer 1

String str1, str2;

Assuming the lengths of the strings are equal:

int i = 0;

for(char c : str1.toCharArray())
{
   if(c != str2.charAt(i++))
      counter++;
}

if(counter > 1)
  // mismatch

Answer 2

Compare the strings one character at a time.Keep a counter to count the mismatch.When the counter exceeds the limit, return false.If you reach the end of string, return true

Answer 3

Try this to store the strings in a char array (char[] charArray = String.toCharArray()).

char[] stringA = firsString.toCharArray();
char[] stringB = secondString.toCharArray();
int ctr = 0;   

if(stringA.length == stringB.length){
    for(int i = 0; i<stringA.length; i++){
        if(stringA[i] == stringB[i]){
           ctr++;
        } 
    }
}

//do the if-else here using the ctr

Answer 4

If you want the FASTEST way, you should code it from an existing algorithm like "Approximate Boyer-Moore String Matching" or Suffix Tree method...

Look at here: https://codereview.stackexchange.com/questions/13383/approximate-string-matching-interview-question

They did the math, you do the code...

Other interesting SO posts are:

Getting the closest string match

Can java.util.regex.Pattern do partial matches?

Generating all permutations of a given string

Similarity Score - Levenshtein