This is pretty easy for distance 1. Generating all possibilities for distances > 1 becomes somewhat more complex.
Start with a word:
$input = 'word';
Split the word into letters and generate a list of replacements.
$letters = str_split($input);
$alphabet = range('a', 'z');
Deletions are the easiest, just loop over each position and replace with ''
:
foreach ($letters as $i => $letter) {
$variants[] = substr_replace($input, '', $i, 1);
}
Insertions and replacements can be done at the same time, because they'll both require a loop over the letters in the input nested inside a loop over the alphabet.
foreach ($alphabet as $variation) {
foreach ($letters as $i => $letter) {
// insertion
$variants[] = substr($input, 0, $i) . $variation . substr($input, $i);
// substitution
// (check that the letter is different or you'll get multiple copies of the input)
if ($variation != $letter) {
$variants[] = substr_replace($input, $variation, $i, 1);
}
}
$variants[] = $input . $variation; // handle insertion at the end
}
You can check the results to verify the levenshtein distances are correct:
foreach ($variants as $variant) {
$result[$variant] = levenshtein($input, $variant);
}