Google #4 Edit Distance

Writer: Steven, Lee

Date: 4/3, Wednesday

Purpose: Solving #72 Edit Distance (Dynamic Programming)

 

Level: Hard

Percentage: 36.9% have solved this problem

Time: it took me an 1 hour :)

Time Complexity: O(n^2) worst case

Runtime:  4 ms, faster than 96.00% of Java submissions

 

 

한국어 버전은 밑에 있습니다.

 

 

* Caution * Before you read the solution that I used, you need to solve this problem by yourself 

 

 

 

* Description *

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

 

* Example *

Example 1:

Input: word1 = "horse", word2 = "ros"

Output: 3

Explanation:

$ horse -> rorse (replace 'h' with 'r')   $

$ rorse -> rose (remove 'r')               $

$ rose -> ros (remove 'e')                 $

 

 

Example 2:

Input: word1 = "intention", word2 = "execution"

Output: 5

Explanation: 

$ intention -> inention (remove 't')              $

$ inention -> enention (replace 'i' with 'e')     $

$ enention -> exention (replace 'n' with 'x')    $

$ exention -> exection (replace 'n' with 'c')     $

$ exection -> execution (insert 'u')                $

 

 

 

 

 

* Idea *

We can solve it with dynamic programming skill. Firslty, Let's make the function to solve this problem. F(i, j) means minimum costs to convert a single character of word 1 to a single character of word 2. there are two cases to define the function.

 case 1: if word1[i] == word2[j], then F(i, j) = F(i-1, j-1)

 case 2: if word1[i] != word2[j], then F(i, j) = min( F(i-1, j-1), F(i-1, j), F(i, j-1)) + 1  

              1. F(i - 1, j) represents insert operation

              2. F(i, j - 1) represents delete operation

              3. F(i - 1, j - 1) represents replace operation 

Let me explain more detail about this. I think obviously you can understand why it can be sperated into two cases. The main subject we need to talk about is how the defintion of the function is derived, how the function looks like this F(i, j) = F(i-1, j-1) when word1[i] == word2[j] so on. I would like to give you an example to let you know it easily.

 * Here is the example *

word1 = intention, word2 = execution

map:

          i     n     t     e     n     t     i     o    n

     0   1     2    3     4     5     6    7     8    9

e   1    1     2    3     3     4     5    6     7    8  

x   2    2

e   3    3

c   4    4

u  5    5

t   6    6

i   7    6

o  8    7

n  9    8

 word1[0] ('i') != word2[0] ('e'). Here, word1 is "i" and word2 is "e". What we use here is "replace". Indeed, map[i-1][j-1] represents the string being converted from word1 to word2. so map[i-1][j-1] + 1 can be treated as "replace". Also, it's the reason why map[i][j] = map[i-1][j-1] when word1[i] = word2[j]. it doesn't convert any single character. you can check out word1[3] ('e') and word2[0] ('e') it's followed by map[i-1][j-1]

 Let's look at word1[4] ('n') and word2[0] ('e'). Here, word1 is "e" and word2 is "e". Why word1 is "e" is because it took 3 times to convert from "inte" to "e" (delete "i", "n", "t"). And This time map[i][j] followed map[i][j-1] + 1. Why?? we need to delete 'n' therefore, map[i][j-1] must lowest number in three options.

 Lastly, Let's look at word1[0] ('i') and word2[7] ('o'). Here, word1 is "executi" and word2 is "exectio" This time map[i][j] followed map[i-1][j] + 1. Because we need to insert 'o' therefore, map[i-1][j] must lowest number in three options.

After you fill the map with numbers, Return map[map.length-1][map[0].length-1]. That's it

   

 

 

 

(한국어)

 

* 난이도: 어려움 *

* 오직 36.9%만이 이 문제를 풀었습니다. *

* 저는 1시간 정도가 걸렸습니다. *

* 시간 복잡도는 O(n^2)입니다 *

* 런타임은 4ms로 자바로 제출한 96.00%보다 빠릅니다. *

 

 

 

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

 

 

* 지문 *

 두개의 문자인 word1과 word2가 주어진다. word1에서 word2로 변환하는 데 필요한 최소 오퍼레이션의 수를 구하여라. 

다음 3가지의 오퍼레이션을 사용할 수 있다:

1. 한 글자를 삽입
2. 한 글자를 삭제
3. 한 글자를 교체

 

 

* 예시 *

예시 1:

입력: word1 = "horse", word2 = "ros"

출력: 3

설명:

$ horse -> rorse (' h'를 'r'로 교체한다 )   $

$ rorse -> rose ( 'r'을 제거한다. )           $

$ rose -> ros ( 'r'을 제거한다. )              $

 

 

Example 2:

입력: word1 = "intention", word2 = "execution"

출력: 5

설명: 

$ intention -> inention ( 't'를 제거한다. )           $

$ inention -> enention ( 'i'를 'e'로 교체한다. )     $

$ enention -> exention ( 'n'를 'x'로 교체한다. )    $

$ exention -> exection ( 'n'를 'c'로 교체한다. )     $

$ exection -> execution ( 'u'를 삽입한다. )           $

 

 

 

 

 

* 아이디어 *

 이 문제는 동적계획법을 사용하면 쉽게 풀 수 있습니다. 첫 번째로, 이 문제를 풀기 위한 함수를 만드는 것으로 시작하겠습니다. F(i, j)는 word1의 한 글자가 word2의 한 글자로 바꿔지는 최소한 비용을 의미합니다. 이 함수를 정의하는데 두 가지 조건이 있습니다.

 case 1: 만약 word1[i] == word2[j], 그렇다면 F(i, j) = F(i-1, j-1)

 case 2: 만약 word1[i] != word2[j], 그렇다면 F(i, j) = min( F(i-1, j-1), F(i-1, j), F(i, j-1)) + 1  

              1. F(i - 1, j) 삽입을 의미합니다.

              2. F(i, j - 1) 삭제를 의미합니다.

              3. F(i - 1, j - 1) 교체를 의미합니다. 

 

 이것에 대해서 더 자세히 설명하겠습니다. 제 생각에는 독자분들은 왜 함수가 두 가지 조건으로 나뉘어지는지 이해할 것이라고 생각됩니다. 주요 포인트는 어떤 식으로 이 함수가 도출되었는지 다뤄보는 것입니다. 어떤 식으로 이 함수가 word1[i] == word2[j]일 때 F(i, j) = F(i-1, j-1)가 되는지 얘기해야 된다고 생각합니다. 쉽게 설명하기 위해 예시를 들어보겠습니다.

 * 예시입니다 *

word1 = intention, word2 = execution

map:

          i     n     t     e     n     t     i     o    n

     0   1     2    3     4     5     6    7     8    9

e   1    1     2    3     3     4     5    6     7    8  

x   2    2

e   3    3

c   4    4

u  5    5

t   6    6

i   7    6

o  8    7

n  9    8

 word1[0] ('i') != word2[0] ('e'). 여기서 word1은 "i"이고 word2는 "e"입니다. 그리고 "교체"를 사용해야 할 것입니다. 사실, map[i-1][j-1]은 word1에서 word2로 바꾸어지고 있는 문자열을 의미합니다. 그렇기에 map[i-1][j-1] + 1은 "교체"로 쓸 수 있는 것입니다. 또한 왜 word1[i] = word2[j]일 때, map[i][j] = map[i-1][j-1]이 되는지 이유가 됩니다. 어떤 한 글자도 바뀔 이유가 없기 때문입니다. word1[3] ('e') 그리고 word2[0]('e')에서 확인이 가능합니다. 이것은 map[i-1][j-1]으로부터 도출되었습니다. 

 word1[4] ('n') 그리고 word2[0] ('e')를 살펴보겠습니다. 여기서 word1은 "e" 그리고 word2는 "e"입니다.  word1이 "e"이 된 이유는 "inte"에서 "e"를 교체하기 위해 3번을 삭제했기 때문입니다. ("i", "n", "t"를 삭제) 그리고 이번에는 map[i][j-1] + 1을 사용했습니다. 그 이유는 'n'을 삭제하기 위함입니다. 그래서 map[i][j-1]이 세 가지 옵션중에서 가장 작은 숫자가 되는 것입니다.

 마지막으로 word1[0] ('i') 그리고 word2[7] ('o')를 살펴보겠습니다. 이번에는 word1는 "executi"이고 word2는 "exectio"입니다. 이번에는 map[i][j]는 map[i-1][j] +1입니다. 왜냐하면 이번에는 'o'를 추가해야 하기 때문입니다. 그러므로 map[i-1][j]은 세 가지 옵션중에서 가장 적은 숫자가 됩니다.

map을 숫자들로 채운 뒤에 map[map.length-1][map[0].length-1]을 반환합니다. 수고하셨습니다. 

 

 

 

 

 

 

 

* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

public class EditDistance_72 {
    public static int minDistance(String word1, String word2) {
        if(word1.length() * word2.length() == 0) {
        	return word1.length() > word2.length() ? word1.length() : word2.length();
        }
        
        char[] c1 = word1.toCharArray();
        char[] c2 = word2.toCharArray();
    	
    	int[][] map = new int[c1.length+1][c2.length+1];
        map[0][0] = 0;
        
       for(int i = 1 ; i < map[0].length ; i++) { map[0][i] = i; }
       for(int i = 1 ; i < map.length ; i++) { map[i][0] = i; }
       
       for(int i = 1 ; i < map.length ; i++) {
    	   for(int j = 1 ; j < map[0].length ; j++) {
    		   if(c1[i-1] == c2[j-1]) map[i][j] = map[i-1][j-1];
    		   else {
    			   map[i][j] = Math.min(Math.min(map[i-1][j], map[i][j-1]), map[i-1][j-1]) + 1;
    		   }
    	   }
       }   
       
       return map[map.length-1][map[0].length-1];
    }

	public static void main(String[] args) {
		int res = minDistance("intention", "execution");
		System.out.println("Result: " + res);
	}

}