두 스트링일 같게 만드는데 최소한의 연산 횟수를 구하는 문제이다.
추가, 삭제, 교체 이렇게 3가지 연산이 가능하다.
잘 생각해보면 이것도 순차적으로 char을 하나씩 추가해가며 이전 결과를 활용할 수 있다.
dp[0][3]이 의미하는 것은 빈 스트링을 "hor"으로 만들려면 몇번의 연산이 필요한지 이다. 3번의 추가가 필요하니 3이 저장된다.
아래처럼 초기값을 세팅해준다.
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
h를 r로 만들어야 한다. 마지막 char이 다르니까 추가든 삭제든 교체는 어떤 작업이 필요하다.
h 삭제 + 빈 스트링을 r로 만드는 작업횟수 1 = 2
h를 빈스트링으로 만드는 작업횟수 1 + r 추가 = 2
빈 스트링을 빈스트링으로 만드는 작업횟수 0 + r 추가 = 1
헷갈릴때에는, 이 전 계산해놓은 값의 결과에서 어떤연산을 추가로해놓으면 되는지 생각해본다.
(ex. h를 빈스트링으로 만드는데 1개연산이 들었네? 그럼 빈스트링이 결과이니까 여기에 r만 추가하면 되는거네.)
ref: https://youtu.be/MiqoA-yF-0M
time O(N^2) space O(N^2)
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(w1, w2) {
if(w1===w2) return 0;
w1="#"+w1;
w2="#"+w2;
const dp = [...Array(w1.length)].map(row => Array(w2.length).fill(0));
for(let i=0; i<w1.length; i++){
for(let j=0; j<w2.length; j++){
if(i===0){
dp[0][j]=j;
continue;
}
if(j===0){
dp[i][0]=i;
continue;
}
if(w1[i]===w2[j]){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1;
}
}
}
return dp[w1.length-1][w2.length-1];
};