202.距離の編集
16427 ワード
2つの文字列
A, B
が与えられると、A
がB
となるように編集される.次の3つの演算を実行できます.
「挿入」(Insert):特定の場所に文字を挿入します.
削除(Remove):特定の場所で文字を削除します.
置換(Replace):特定の位置の文字を異なる文字で置換します.
一度に1つしか選択できません.
このとき最小編集回数を求める.
入力条件
2つの文字列
A
とB
の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';
}
Reference
この問題について(202.距離の編集), 我々は、より多くの情報をここで見つけました https://velog.io/@corone_hi/202.-편집-거리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol