[Java] leetcode 72. Edit Distance

문제

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

알아야 할 개념

• 다이나믹 프로그래밍 

풀이

문제에서 문자를 삭제, 추가, 교체 하는 작업을 하나의 단위로 주어졌다. 

 

풀이는 다음과 같다.

1. 주어진 문자열 2개를 문자 배열로 만든다.
2. 선형 탐색으로 0행과 0열을 초기화 한다.
3. 2중 for문을 돌면서 다음을 수행한다. 
   1. 문자열 1 의 i 번째 문자와, 문자열 2 의 j번째 문자가 같으면 [i-1][j-1] 의 값을 가져온다.
   2. 다르면, 현재 위치 (i 행 j 열) 에서 [i-1][j] , [i-1][j-1] , [i][j-1] 3개의 값의 최솟값에 1 을 더한 값을 할당한다.
4. 정답을 리턴한다.

 

문자열 연산 수의 최솟값 구하기 는 잘 알려진 알고리즘이다. 다음과 같은 문자열 "ab" 와 "cda" 가 있다고 가정하면

dp table 은 다음과 같다.. (null 은 공백이다)

이때 dp[i][j] 의 값의 뜻은 현재 i j 위치에서( 문자열 1 [ 0.. i-1] 문자열 2 [0 .. j-1]  ) 문자열 1 , 2 같게 만드는 최소값.임을 알아두자. 

  문자열 1 을 문자열 2 로 바꾸는 과정에서. 오른쪽으로는 추가연산, 아래쪽 방향은 삭제 연산을 의미한다, 대각선 방향은 교체 연산을 의미한다.

	null	c	d	a
null
a
b

0행의 최소 연산 값을 초기화 해준다..  문자열 1의 "" , "a" , "ab" 들을 null 로 만드는 과정임으로 삭제 연산을 진행한다. 따라서 +1 을 해준다.

 

	null	c	d	a
null	0
a	1 ( "a" 에서 "a" 삭제)
b	2 ("b" 에서 "b" 삭제)

같은 알고리즘으로 0열벡터를 초기화 한다.

 

	null	c	d	a
null	0	1("" 에서 "c" 추가)	2 ("c" 에서 "d" 추가)	3 ("cd" 에서 "a" 추가)
a	1 ( "a" 에서 "a" 삭제)
b	2 ("b" 에서 "b" 삭제)

 

이제 1행 1열부터 끝까지 2중 for문으로 풀이 알고리즘 3을 수행한다

현재 위치에서 문자열1의 i번째 문자와 문자열2 j번째 문자가 일치하면 i-1, j-1 위치의 값을 가져온다. ( 추가연산이 필요하지 않기 때문이고 항상 i-1, j-1 이 최솟값이 보장되있다. )  그리고 문자열 1 원래위치의 문자를 더해주는것은 연산에 포함되지 않기 때문에 추가로 1을 더하지 않는다.

 

현재 위치에서 문자가 일치하지 않으면 3개의 위치에서 최솟값을 비교하면서 더해준다. 손으로 직접 그려보면 쉽게 이해할수 있다.

과정은 다음과 같다. (추가 교체, 삭제 중 아무거나 해도 상관없다 ) 

	null	c	d	a
null	0	1("" 에서 "c" 추가)	2 ("c" 에서 "d" 추가)	3 ("cd" 에서 "a" 추가)
a	1 ( "a" 에서 "a" 삭제)	1("a" 에서 "c" 교체)	2 ("c" 에서 "d" 추가)	2 ("cd" 에서 추가 연산 없음 )
b	2 ("b" 에서 "b" 삭제)	2("a" 에서 "c"교체)	2 ("cb" 에서 "cd"로 교체 )	3 "cdb"에서 "cda" 교체

코드

자바

class Solution {
    public int minDistance(String word1, String word2) {
        int row = word1.length();
        int col = word2.length();
        int dp[][] = new int[row+1][col+1];
        char [] word1Arr = word1.toCharArray();
        char [] word2Arr = word2.toCharArray();
        for(int i = 1 ;i < row+1 ;i++)dp[i][0] = i;
        for(int j = 1; j< col+1;j ++)dp[0][j] = j;
        for(int i = 1 ;i <row+1;i++){
            for(int j= 1; j < col+1;j ++){
                if(word1Arr[i-1] == word2Arr[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] += Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1]))+1;
                }
            }
        }
        return dp[row][col];
    }
}