꿀잠

https://leetcode.com/problems/edit-distance/

이번 문제는 DP 문제로 1번 문자열을 2번 문자열로 변환 시킬 때 삽입,삭제,대체 의 세가지 기능을 이용하여 최소 몇 번으로 변화 시킬 수 있는지 묻는 문제이다. DP 문제라는 것을 알고도 아이디어가 떠오르지 않아 한참 고민하다 결국 정답 영상을 찾아 보고야 말았다. 정답을 확인하고 나니 이전에 풀었던 최대 부분 문자열 찾기 문제랑 흡사한 형태였다. 해당 문제는 아래에 있다.

https://leetcode.com/problems/longest-common-subsequence/

이 문제를 풀이 이해하기 위해선 DP 배열 표를 만들어 보면 이해하기 쉽다. 문제에 주어진 예제중 하나인 horse 와 ros 를 기준으로 예외 표를 아래와 같이 그릴 수 있다.

각 좌표에서의 값을 분석해보자 우선 1행과 1열의 값을 보자.
빈 문자열에서 h, ho, hor, hors, hosrse 의 문자열을 만들기 위해선 삽입이란 행동이 필요하므로 1씩 증가한다. 마찬가지의 원리로 1열 또한 증가한다. 임의의 행, 열에서 각각의 행 문자와 열 문자가 같다면 i - 1, j - 1의 값과 같다. 예를 들어 hors 와 ros 의 최소 변환 값은 hor과 ro의 변환 값과 같다. 마지막 s는 변환이 필요 없기 때문이다. 따라서 i - 1, j - 1인 hor, ro의 값과 같다는 점을 알 수 있다.

한편 행과 열의 추가 문자가 다른 경우를 보자 ho와 r의 경우 2이다. 이 경우는 h, r 에서 o를 삭제하는 행위가 추가되는 경우이고, , h,""의 경우의 수에 o를 r로 대체하는 경우의 수가 추가되는 경우이다. 이처럼 i - 1의 경우 삽입의 경우의 수가 늘어나고, j - 1 의 경우 삭제의 경우의 수가 늘어나는 경우, 그리고 i - 1, j - 1 의 경우 대체의 경우의 수가 늘어나는 경우이다.

특정 i, j 에서 글자 수가 생성된다면 이 경우의 수에 한 번의 삽입, 삭제, 대체로 변환 시킬 수 있다. 따라서 최소 변환 방법은 (i, i - 1), (j, j - 1), (i - 1, j - 1)의 값 중에서 가장 작은 값에 1을 추가 시킨 경우이다. 이를 이용하여 점화 식을 만들어 해결하면 아래와 같은 코드가 나온다.

 public class Solution {  
    public int minDistance(String word1, String word2) {  
        int m = word1.length() + 1;  
        int n = word2.length() + 1;  
  
        int[][] dp = new int[m][n];  
  
        for(int i = 0; i < m; i++){  
            dp[i][0] = i;  
        }  
  
        for(int j = 0; j < n; j++){  
            dp[0][j] = j;  
        }  
  
        for(int i = 1; i < m; i++){  
            char c1 = word1.charAt(i - 1);  
            for(int j = 1; j < n; j++){  
                char c2 = word2.charAt(j - 1);  
                if(c1 == c2){  
                    dp[i][j] = dp[i - 1][j - 1];  
                }else{  
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;  
                }  
            }  
        }  
  
        return dp[m - 1][n - 1];  
    }  
}