The problem is very similar to the Levenshtein distance problem so I won’t write out the full solution code but will direct you to resources online.
The Levenshtein distance is an edit distance metric. An Edit distance metric is used to determine how similar a source word is to a target word. The allowed operations to transform a source word to a target word are insertion, deletion, and substitution. An aside: there’s another edit distance metric called the Damerau–Levenshtein distance. I advise that you check this one out. It adds another operation to the suite of available operations on the source word: the transposition of adjacent characters.
Let correspond to the source and the target word respectively. The person who knows how to speak English the best (according to me – might be a slack metric but it works) is the person who scored .
The recurrence relation is defined on the wikipedia page for the Levenshtein distance. Plus, there’s also some pseudocode that should guide you on how to solve the puzzle.
Some more hints:
- Remember that the cost for insertion and deletion should be the same (maybe, 1).
- The cost of substitution should be strictly less than the cost of deletion or insertion (maybe, 0.5).
Y’all can take it from here!