CSES 3. Edit Distance (1639)

출처:  https://cses.fi/problemset/task/1639

---

문제 설명

The edit distance between two strings is the minimum number of operations required to transform one string into the other.

The allowed operations are:

• Add one character to the string.
• Remove one character from the string.
• Replace one character in the string.

For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.

Your task is to calculate the edit distance between two strings.

입력 

The first input line has a string that contains n characters between A–Z.

The second input line has a string that contains m characters between A–Z.

출력

Print one integer: the edit distance between the strings.

입력 예

LOVE
MOVIE

출력 예

2

제약조건

1 <= n,m <= 5000

---

문제 풀이

두개의 문자열을 행과 열로 하는 테이블을 생각한다. src[i] == dest[j]는 변경할 필요가 없으며 값을 변경하지 않아도 된다. 문자열이 다르면, dist[i][j] = min({dist[i][j-1], dist[i-1][j], dist[i-1][j-1]) + 1 로 계속 변경해서 테이블을 완성한다.

프로그램 내용

...
for(int i=0; i <= m; ++i)
{
	for (int j=0; j <= n ; ++j)
	{
		if ( i == 0)
        	dist[i][j] = j; /// init for desStr
		else if ( j == 0)
        	dist[i][j] = i; /// init for srcStr
		else if ( srcStr[i-1] == desStr[j-1])
        	dist[i][j] = dist[i-1][j-1];
		else
        	dist[i][j] = 1 + min({	dist[i-1][j],      /// insert
									dist[i][j-1],      /// remove
									dist[i-1][j-1]});   /// replace
	}
}
...

 

Dynamic Programming ( link )