LeetCode 72. Edit Distance(java)
You have the following 3 operations permitted on a word:
a) Insert a character b) Delete a character c) Replace a character
사고방식: 동적 기획 해
DP: dp[i][j] word1 i word2 j 。
case1 : (word1[i] == word2[j]) dp[i][j] = dp[i-1][j-1];
case2 : (word1[i] == word2[j]) insert: dp[i][j] = dp[i][j-1];
delete: dp[i][j] = dp[i-1][j];
replace: dp[i][j] = dp[i-1][j-1];
base case: dp[i][0] = dp[0][i] = i;
코드:
public int minDistance(String word1, String word2) {
if (word1.length() == 0) return word2.length();
if (word2.length() == 0) return word1.length();
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) dp[i][0] = i;
for (int i = 0; i < n; i++) dp[0][i] = i;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = dp[i - 1][j -1 ];
} else {
int insert = dp[i][j - 1];
int delete = dp[i - 1][j];
int replace = dp[i -1][j - 1];
dp[i][j] = Math.min(insert, Math.min(delete, replace));
dp[i][j]++;
}
}
}
return dp[m][n];
}
// dp , : m*n ,pre ,temp , 。
public int minDistance(String word1, String word2) {
if (word1.length() == 0) return word2.length();
if (word2.length() == 0) return word1.length();
int m = word1.length(), n = word2.length();
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) dp[i] = i;
for (int i = 1; i <= m; i++) {
int temp = 0, pre = i - 1;
dp[0] = i;
for (int j = 1; j <= n; j++) {
temp = dp[j];
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[j] = pre;
} else {
dp[j] = Math.min(dp[j], Math.min(dp[j-1], pre));
dp[j]++;
}
pre = temp;
}
}
return dp[n];
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.