202.距離の編集



  • 2つの文字列A, Bが与えられると、ABとなるように編集される.

  • 次の3つの演算を実行できます.

  • 「挿入」(Insert):特定の場所に文字を挿入します.

  • 削除(Remove):特定の場所で文字を削除します.

  • 置換(Replace):特定の位置の文字を異なる文字で置換します.

  • 一度に1つしか選択できません.

  • このとき最小編集回数を求める.

  • 入力条件

  • 2つの文字列ABの1行1つ.

  • 各文字列は英字のみで構成され、各文字列の長さは1以上、5000以下である.

  • しゅつりょくじょうけん
    出力
  • 最小編集距離.
  • 1.動的プログラミング

    
    def edit_dist(str1, str2):
      n = len(str1)
      m = len(str2)
    
      dp = [[0] * (m + 1) for _ in range(n + 1)]
      for i in range(1, n + 1):
        dp[i][0] = i #첫행 초기화
      for j in range(1, m + 1):
        dp[0][j] = j #첫열 초기화
    
      for i in range(1, n + 1):
       for j in range(1, m + 1):
         #문자가 같다면 왼쪽 위에 해당하는 수를 그대로 대입
         if str1[i - 1] == str2[j - 1]:
           dp[i][j] = dp[i - 1][j - 1]
         #문자가 다르다면, 3가지 경우 중에서 최솟값 찾기
         else: #삽입(왼쪽), 삭제(위쪽), 교체 (왼쪽 위) 중에서 최소 비용
          dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
    
      return dp[n][m]
    
    str1 = input()
    str2 = input()
    
    print(edit_dist(str1, str2))
    
    

    2. C++

    #include <bits/stdc++.h>
    
    using namespace std;
    
    // 두 문자열을 입력 받기
    string str1;
    string str2; 
    
    // 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
    int editDist(string str1, string str2) {
        int n = str1.size();
        int m = str2.size();
    
        // 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
        vector<vector<int> > dp(n + 1, vector<int>(m + 1));
    
        // DP 테이블 초기 설정
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = j;
        }
    
        // 최소 편집 거리 계산
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
                else { // 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                    dp[i][j] = 1 + min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }
    
        return dp[n][m];
    }
    
    int main(void) {
        cin >> str1 >> str2;
    
        // 최소 편집 거리 출력
        cout << editDist(str1, str2) << '\n';
    }