Weighted edit distance

Similar to Levenshtein distance (Edit distance)

Weight of an operation depends on the character(s) involved.

Meant to capture OCR / keyboard errors.

e.g. m more likely to be mis-typed as n than as q.

Therefore, replacing m by n is a smaller edit distance than by q.

Requires a weighted matrix as input.

Modify DP to handle weights.

Given a misspelled query - do we compute its edit distance to every dictionary term?