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.

It is called [Levenshtein distance](http://en.wikipedia.org/wiki/Levenshtein_distance). — jlordo, Dec 19 '12 at 10:30

score 1 · Accepted Answer · answered Dec 19 '12 at 10:30

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

answered Dec 19 '12 at 10:30

Juvanis

25,802
5
69
87

1

you could even `if (++counter > 1) break;` to avoid continuing once you have found that the mismatch is greater than 1. – assylias Dec 19 '12 at 10:42

score 1 · Answer 2 · answered Dec 19 '12 at 10:30

1

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

answered Dec 19 '12 at 10:30

Renjith

3,274
19
39

score 1 · Answer 3 · answered Dec 19 '12 at 10:34

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

score 1 · Answer 4 · edited May 23 '17 at 12:09

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...

Java match string with x allowed mismatches.

4 Answers4