[LeetCode 문제 풀이] 72. 거리 편집 (Java)

글 목록

(1) 72. 편집 거리

(1) 72. 거리 편집
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:
Insert a character Delete a character Replace a character 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')

참고:https://leetcode.com/problems/edit-distance/discuss/25849/Java-DP-solution-O(nm)

이 문제 코드 는 64. Minimum Path Sum 과 매우 비슷 하지만 분석 하기 가 더욱 어렵다.

이들 의 분석 방식 은 비슷 하 다. 모두 통 해 를 찾 은 다음 에 특 해 를 구 하 는 것 이다.그리고 한 줄 한 열 을 초기 화한 다음 에 최소 값 을 찾 습 니 다

문자열 워드 1 과 워드 2 에 대해 f (i, j) 를 정의 하 는 것 은 워드 1 의 전 i 문자 와 워드 2 의 전 j 문자 가 같 아야 하 는 최소 절 차 를 나타 낸다.

만약 에 워드 1 의 i 번 째 와 워드 2 의 j 번 째 가 같다 면 조작 할 필요 가 없다. 즉, f (i, j) = f (i - 1, j - 1)

다 르 면 교체, 삭제, 추가 작업 이 필요 하 다 면 f (i, j) = min (f (i - 1, j - 1), f (i - 1, j), f (i, j - 1) + 1

전체적으로 말 하면 절 차 는 1. 초기 값 (첫 줄 첫 번 째 열) 을 설정 하 는 것 이다. 2. 배열 을 옮 겨 다 니 며 각 점 의 최소 값

을 얻는다.

package DynamicProgramming.EditDistance;

public class Solution {
	public static int minDistance(String word1, String word2) {
		int len1 = word1.length();
		int len2 = word2.length();
		int[][] cost = new int[len1+1][len2+1];

		for(int i=1; i <= len1; i++){ //      
			cost[i][0] = i;
		}

		for(int i=1; i <= len2; i++){ //      
			cost[0][i] = i;
		}

		for(int i=1; i <= len1; i++){
			for(int j=1; j <= len2; j++){
				if(word1.charAt(i-1) == word2.charAt(j-1)){
					cost[i][j] = cost[i-1][j-1];
				} else{
					cost[i][j] = findMin(cost[i-1][j-1],cost[i-1][j],cost[i][j-1]);
					cost[i][j] += 1;
				}
			}
		}

		return cost[len1][len2];
	}

	public static int findMin(int a, int b, int c){ //          
		int min = a < b ? a : b;
		min = min < c ? min : c;
		return min;
	}

	public static void main(String[] args){
		String word1 = "horse";
		String word2 = "ros";
		System.out.println(minDistance(word1,word2));
	}
}