Der einfachste Ansatz, den ich denken kann, ist eine Funktion zu schreiben, die den Grad der Nichtübereinstimmung zurück zwischen zwei Wörtern, und Sie durchlaufen alle Wörter und finden die besten.
Ich habe dies mit einer Branch-and-Bound-Methode getan. Lassen Sie mich den Code ausgraben:
bool matchWithinBound(char* a, char* b, int bound){
// skip over matching characters
while(*a && *b && *a == *b){a++; b++;}
if (*a==0 && *b==0) return true;
// if bound too low, quit
if (bound <= 0) return false;
// try assuming a has an extra character
if (*a && matchWithinBound(a+1, b, bound-1)) return true;
// try assuming a had a letter deleted
if (*b && matchWithinBound(a, b+1, bound-1)) return true;
// try assuming a had a letter replaced
if (*a && *b && matchWithinBound(a+1, b+1, bound-1)) return true;
// try assuming a had two adjacent letters swapped
if (a[0] && a[1]){
char temp;
int success;
temp = a[0]; a[0] = a[1]; a[1] = temp;
success = matchWithinBounds(a, b, bound-1);
temp = a[0]; a[0] = a[1]; a[1] = temp;
if (success) return true;
}
// can try other modifications
return false;
}
int DistanceBetweenWords(char* a, char* b){
int bound = 0;
for (bound = 0; bound < 10; bound++){
if (matchWithinBounds(a, b, bound)) return bound;
}
return 1000;
}
Ich wusste nicht einmal, wie ein solcher Algorithmus existiert !!! – ak3nat0n