Step-by-Step
[Java] Daily LeetCode Challenge 72. Edit Distance ★ 본문
https://leetcode.com/problems/edit-distance/description/
DP 사용해서 문제인데, 사실 너무 감이 오지 않아서 여러 검색을 통해 푸는 방법을 알아보았다.
지금까지 풀어본 몇 안 되는 Hard 유형 중에서 가장 어려웠던 문제.. 유튜브 설명을 보고 공부했다.
다음에 또 다시 풀어봐야함!
유튜브 참조 : https://www.youtube.com/watch?v=b6AGUjqIPsA
[코드]
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length(), len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i=1; i <= len1; i++)
dp[i][0] = i;
for(int i=1; i<= len2; i++)
dp[0][i] = i;
for(int i=1; i <= len1; i++){
for(int j=1; j <= len2; j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else // (대체, 삽입, 제거 => 비용 1) + (가장 최솟값)
dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
}
}
return dp[len1][len2];
}
}
'언어 > JAVA' 카테고리의 다른 글
Comments