leetcode:Edit Distance 편집 거리
1391 단어 leetcode
제목의 뜻은 단어word1과 단어word2를 제시하는 것이다. 우리는 세 가지 방식으로 단어word1을 word2로 바꿀 수 있다. 세 가지 방식은 다음과 같다.
1 문자 삽입
2 문자 하나 삭제
3 문자 대체
-- 워드1에서 워드2로 전환하는 최소 절차는 얼마인가.
먼저 상태 DP[i][j]를 정의하고, DP[i][j]는 단어 1word1[1~i]을 단어 2word[1~j]로 바꾸는 최소 절차를 DP[i][j]로 표시한다.
그러면 우리는 상태 이동 방정식을 얻어낼 수 있다.
워드1의 마지막이 워드2의 마지막과 같을 때.
DP[i][j] = DP[i - 1][j-1];그러니까 이런 식으로 바꿀 필요가 없다는 거예요.
마지막에 다를 때.
그러면 있을 거예요.
DP[i][j] = DP[i ][j - 1] +1;문자 삽입
DP[i][j] = DP[i - 1][j] + 1;문자 삭제
DP[i][j] = DP[i - 1][j - 1] +1;문자 대체
그러면 DP[i][j]는 최소로 하는 거예요.
public class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for(int i = 0; i <= word1.length(); ++i){
dp[i][0] = i;
}
for(int i = 0; i <= word2.length(); ++i){
dp[0][i] = i;
}
for(int i = 1; i <= word1.length(); ++i){
for(int j = 1; j <= word2.length(); ++j){
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i - 1][j - 1]) , dp[i][j - 1]) + 1;
}
}
}
return dp[word1.length()][word2.length()];
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
