編集距離 aoj 動的計画法 レーベンシュタイン距離

DPL_1_E レーベンシュタイン距離

DPL_1_E レーベンシュタイン距離
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=ja#

解説

TODO

計算量

$O(N^2)$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define MAX_S 1001

string S1, S2;
Int dp[MAX_S][MAX_S];

void input() {
  cin >> S1 >> S2;
}

void solve() {
  loop(c1,0,S1.length()+1) {
    loop(c2,0,S2.length()+1) {
      if (c1 == 0) dp[c1][c2] = c2;
      else if (c2 == 0) dp[c1][c2] = c1;
      else if (S1[c1-1] == S2[c2-1]) {
        dp[c1][c2] = dp[c1-1][c2-1];
      } else {
        dp[c1][c2] = 1 + min(min(dp[c1-1][c2], dp[c1][c2-1]), dp[c1-1][c2-1]);
      }
    }
  }

  cout << dp[S1.length()][S2.length()] << endl;
}

int main() {
  input();
  solve();
}