출처: 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 )
'CSES' 카테고리의 다른 글
CSES 3. Money Sum (1745) (0) | 2020.07.29 |
---|---|
CSES 3. Rectangle Cutting (1744) (0) | 2020.07.28 |
CSES 4. Road Reparation (1675) (0) | 2020.01.20 |
CSES 7. Stick Game (1729) (0) | 2020.01.19 |
CSES 4. Road Construction (1676) (0) | 2020.01.13 |