割り当ては、再帰関数に従う最悪のシナリオで、時間計算量がΩ（2 max（n、m） ）であることを示すことです。
次のように想定します。
- n = w1len（単語の長さw1）、
- m = w2len（単語の長さw2）
これがコードです
int dist(String w1, String w2, int w1len, int w2len) {
if (w1len == 0) {
return w2len;
}
if (w2len == 0) {
return w1len;
}
int res = dist(w1, w2, w1len - 1, w2len - 1) + (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);
int addLetter = dist(w1, w2, w1len - 1, w2len) + 1;
if (addLetter < res)
res = addLetter;
int deleteLetter = dist(w1, w2, w1len, w2len - 1) + 1;
if (deleteLetter < res)
res = deleteLetter;
return res;
}