レーベンシュタイン距離
二つの文字列がどれぐらい異なっているかを示すやーつ
Aという文字列に1文字ずつ挿入/削除/置換してBという文字列に変えるまでの最小回数
動的計画法によるアルゴリズムを用いて計算されることが多い
rubyのdid_you_meanもレーベンシュタイン距離を用いているようだ