행 편집 거리 Edit Distance - 동적 계획
1508 단어 알고리즘 학습
제목 설명:
소스 및 대상 열을 지정하여 소스 열을 다음과 같이 조작할 수 있습니다. 1.위치 설정에 문자를 삽입합니다.임의의 문자 바꾸기 3.임의의 문자 삭제
프로그램을 작성하여 최소 조작수를 되돌려줍니다. 이 조작을 하면 목표 직렬과 같고, 원본 직렬과 목표 직렬의 길이는 2000보다 작습니다.
아이디어:
상태 dp[i][j]를 설정하면 원본 직렬 s[0...i]와 목표 직렬 t[0...j]의 가장 짧은 편집 거리를 표시합니다
경계: dp[i][0] = i, dp[0][j] = j
점차적 방정식:
상태 dp[i][j]를 설정하면 원본 직렬 s[0...i]와 목표 직렬 t[0...j]의 가장 짧은 편집 거리를 표시합니다
경계: dp[i][0] = i, dp[0][j] = j
점차적 방정식:
s에 t[j], dp[i][j]=dp[i][j-1]+1 추가하기;
s와 t를 교체하고 dp[i][j]=dp[i-1][j-1]+1;
따라서 상태 전환 방정식을 작성할 수 있습니다.
dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1] + (s[i]==t[j] ? 0 :1))
각각 대응: 삭제, 추가, 교체(같으면 교체하지 않음)
코드:
class Solution {
public:
int minDistance(string word1, string word2) {
int Slen = word1.size();
int Tlen = word2.size();
int dp[Slen+1][Tlen+1] = {0};// ： +1， 0
// n n+1
for(int i=1; i<=Slen; i++) // 1
dp[i][0] = i;
for(int j=1; j<=Tlen; j++)
dp[0][j] = j;
for(int i=1; i<=Slen; i++)
{
for(int j=1; j<=Tlen; j++)
{
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
{
int temp = min(dp[i-1][j], dp[i][j-1]);
dp[i][j] = min(temp, dp[i-1][j-1]) + 1;
}
}
}
return dp[Slen][Tlen];
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 매 결점의 왼쪽 아이와 오른쪽 아이를 교환하여 ~2020.8.13~ 학습노트두 갈래 체인 시계를 두 갈래 나무의 저장 구조로 삼아 두 갈래 나무의 각 결점의 왼쪽 아이와 오른쪽 아이를 교환한다. 두 갈래 나무의 순서를 입력하십시오.알림: 두 갈래 나무의 순서 서열은 문자열입니다. 문자가'#...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
