[leetcode][72] Edit Distance

문제 : https://leetcode.com/problems/edit-distance/

---

word1에서 word2를 만들고자 한다. 최소 편집횟수를 구하라.

편집 방법은 총 3가지가 있다. 1) 문자 추가. 2) 문자 삭제. 3) 문자 대체(변경)

---

대표적 DP 문제 중 하나.

dp[i][j] = word1[0..i]를 word2[0..j]로 만들 때 최소 편집횟수.

 

word1[i], word2[j]가 같다면 dp[i][j] = dp[i-1][j-1]. 

word1[i], word2[j]가 다른경우 

   i) 문자 추가 : dp[i][j-1] + 1

   ii) 문자 삭제 : dp[i-1][j] + 1

   iii) 문자 대체 : dp[i-1][j-1] + 1

위 3가지 방법 중 최소값이 dp[i][j]가 된다.

 

이를 열우선방법으로 dp 배열을 다 채웠을 때, dp[word1.size()][word2.size()]가 정답이된다.

 

시간복잡도는 O(NM). N = |word1|, M = |word2|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/72.%20Edit%20Distance.cpp