Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
class Solution {
public int minDistance(String word1, String word2) {
//dp 배열 초기화
int[][] dp=new int[word1.length()+1][word2.length()+1];
//공집합에서 word2를 만들 때의 edit distance, word1을 만들 때의 edit distance를 memoization
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++){
//현재의 문자가 같다면,
//word1, word2 각각 현재 문자 이전까지의 edit distance에 그대로 붙이면 됨
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
//현재의 문자가 다르다면
else{
int replace=dp[i-1][j-1]+1;
int delete=dp[i-1][j]+1;
int insert=dp[i][j-1]+1;
dp[i][j]=Math.min(replace, Math.min(delete, insert));
}
}
}
return dp[word1.length()][word2.length()];
}
}
LCS(Longest Common Subsequence) 알고리즘으로 어떻게 해보려다가 결국 혼자 풀지 못했다. 두 문자의 유사도를 알 수 있는 편집 거리 알고리즘을 사용해서 해결할 수 있다.
😁