Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.
Given two strings S1 and S2, the minimum number of operations to convert one to the other
Operations are typically character-level
Insert, Delete, Replace, (Transposition)
E.g., the edit distance from dof to dog is 1
From cat to act is 2 (Just 1 with transpose.)
from cat to dog is 3.
Generally found by dynamic programming.
See http://www.merriampark.com/ld.htm for a nice example plus an applet.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License