최소거리알고리즘2 [leetcode 72] Edit Distance Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Inp.. 2020. 10. 28. [알고리즘] 최소편집거리 알고리즘 edit distance, Levenshtien distance - 동적프로그래밍을 사용한다. - 서로 다른 문자열 str1과 str2이 같아지기 위해 몇 번의 과정을 거쳐야 하는지 이다. (두 문자열 사이 유사도 측정) - 과정에서 할 수 있는 동작은 insert, delete, replace 아래 3가지이다. 예를 들어 abcdeg를 azcde로 바꾼다면 1. 문자 지우기 : g를 지운다. 2. 문자 삽입 3. 문자 바꿔치기(replace): b를 z로 바꾼다. 가 될 수 있다. 접근방법: 이차원 배열을 사용한다. dp[i][j] dp[i][j]가 의미하는 바는 str1.substr(0,i)와 str2.substr(0,j)사이의 거리를 의미한다. dp[0][0]은 공문자열 사이에서 비교하는 것이기 때문에 거리가 0이다. dp[0][i]는 공문자열과 str.subs.. 2020. 10. 28. 이전 1 다음
