[Leetcode] Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a characterb) Delete a characterc) Replace a character

자연언어처리(NLP)에서 기본적인 문제는 두 문자열minimal Edit Distance을 구하는 것이다. 일명 Levenshtein distance라고도 부른다.한 편Edit Distance 소개의 계발을 받아 본고는 동적 기획으로 두 문자열 사이의 minimal Edit Distance를 구했다.동적 기획 방정식은 다음 문장에서 설명할 것이다.
1. what is minimal edit distance?
간단하게 말하면, 삽입 (insert), 삭제 (delete), 교체 (substitute) 를 통해서만 하나의 문자열 s1을 다른 문자열 s2로 바꾸는 최소 단계 수입니다.알고리즘에 익숙한 학생들은 이것이 동적 기획 문제라는 것을 쉽게 알 수 있다.
사실 교체 작업은 delete + insert와 맞먹을 수 있기 때문에 권한 값을 다음과 같이 정의합니다.
I (insert):1
D (delete):1
S (substitute):2
2. example:
intention->execution
Minimal edit distance:
delete i ; n->e ; t->x ; insert c ; n->u 구화득cost=83.calculate minimal edit distancedynamically 사고방식은 주석을 보십시오. 여기 D[i, j]는 s1 전 i개character와 s2 전 j개character에서 얻은 minimal edit distance입니다.
세 가지 작업 동적 업데이트:
D(i,j)=min { D(i-1, j) +1, D(i, j-1) +1 , D(i-1, j-1) + s1[i]==s2[j] ? 0 : 2};의 세 항목은 각각 D, I, S에 해당합니다.(자세한 내용은 내 동창의 블로그

 1 class Solution {

 2 public:

 3     int minDistance(string word1, string word2) {

 4         int len1 = word1.length();

 5         int len2 = word2.length();

 6         if (len1 == 0) return len2;

 7         if (len2 == 0) return len1;

 8         vector<vector<int> > dp(len1 + 1, vector<int>(len2 + 1));

 9         for (int i = 0; i <= len1; ++i) dp[i][0] = i;

10         for (int j = 0; j <= len2; ++j) dp[0][j] = j;

11         int cost;

12         for (int i = 1; i <= len1; ++i) {

13             for (int j = 1; j <= len2; ++j) {

14                 cost = (word1[i-1] == word2[j - 1]) ? 0 : 1;

15                 dp[i][j] = min(dp[i-1][j-1] + cost, min(dp[i][j-1] + 1, dp[i-1][j] + 1));

16             }

17         }

18         return dp[len1][len2];

19     }

20 };

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[Leetcode] Edit Distance

좋은 웹페이지 즐겨찾기