MediumNLPnlp-047

Fuzzy Match within Edit Distance 1

Problem

Return the sorted list of vocabulary words within Levenshtein edit distance 1 of word, including word itself when it is in the vocabulary.

Return an empty list when no vocabulary item is close enough.

Hint

A distance-1 test only needs one insertion, deletion, or substitution, so a full DP table is enough.

case 1

in: [["cat","bat","car","dog"],"cat"]

expected: ["bat","car","cat"]

case 2

in: [["hello","yellow"],"hell"]

expected: ["hello"]

case 3

in: [["abc"],"xyz"]

expected: []

case 4

in: [["a","ab","abc"],""]

expected: ["a"]

case 5

in: [["book","books","cook","boon"],"bok"]

expected: ["book"]

Starter codePython

def fuzzy_match(vocab, word):
    # Your code here
    pass

5 test cases · run your code against them in the editor