leetcode -- Edit Distance - 중점 dp
2625 단어 LeetCode
여기 dp[i, j], i와 j는 개수로 보고 index로 보지 마세요.그래서 dp[i, j]의 뜻은word1의 앞 i자모와word2 앞 j자모의 edit distance이다.이곳은 가장 긴 공공 서열의 사고방식과 같다.
dp[i, j]에 대해 여기는 dp[i, j-1]에 알파벳을 붙이거나 dp[i-1, j]에 알파벳을 붙이거나 d[i-1, j-1]+1을 붙이면word1[i]이 된다!word2[j]일 때 dp[i-1, j-1]는word1[i]=word2[j]이다.
즉dp[i][j-1] + 1, j에 대응하는 delete 조작 dp[i-1] [j] + 1, i에 대응하는 delete 조작 dp[i-1] [j-1] + (0 if word1 [i]! = word2 [j] else 1, replace 또는 replace 조작 없음
세 가지 조작에서 출발하면 됩니다. 여기는 insert 조작을 고려하지 않습니다.
dp[i,j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + (0 if word1[i] == word2[j] else 1))
참고 자료http://www.cnblogs.com/zuoyuan/p/3773134.html http://zhangbuhuai.com/2015/05/23/edit-distance/#
class Solution:
# @return an integer
def minDistance(self, word1, word2):
m=len(word1)+1; n=len(word2)+1
dp = [[0 for i in range(n)] for j in range(m)]
for i in range(n):
dp[0][i]=i
for i in range(m):
dp[i][0]=i
for i in range(1,m):
for j in range(1,n):
dp[i][j]=min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(0 if word1[i-1]==word2[j-1] else 1))
return dp[m-1][n-1]이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
