Edit Distance - Leet Code

"편집 거리" 알고리즘 문제로, 두 문자열의 유사도를 판단하는데 유용하게 쓰일 여지가 있는 알고리즘이다.

별도로 "편집 거리" 알고리즘이라 정의했으나, Dynamic Programming에 포괄되는 범위로 정의해도 위화감이 있을 것 같지는 않다.

구체적인 구현 방향은 하기와 같다.

1. 첫번째 단어의 a번 인덱스까지의 단어부터 두번째 단어의 b번 인덱스까지 변경하는데 드는 최소 비용을 dp[a][b]로 정의한다.
2. 0번 부터 1 ~ N번까지를 초기화하고,
3. 각 for(int i = 1; i <= word1.size(); i++)
   for(int j = 1; j <= word2.size(); j++)
   구문을 통해 word_1[i], word_2[j]의 값이 일치하는지 확인한 뒤,
   불일치할 경우, dp[i-1][j-1], dp[i][j-1], dp[i-1][j] 중 최솟값 + 1을 순차적으로 할당하는 방향으로 풀이 가능하다.