거리 수정

난이도 하드
자주 묻는 질문 아마존 ByteDance Facebook 구글 Microsoft Palantir Technologies 사각형.
동적 프로그래밍 조회수 36

편집 거리 문제에서 우리는 변환에 필요한 최소 작업 수를 찾아야합니다. 길이가 n 인 X에서 길이가 m 인 다른 문자열 Y까지.

허용 된 작업 :

  1. 삽입
  2. 삭제
  3. 치환

거리 수정

입력:

String1 =“abcd”

String2 = "abe"

출력:

필요한 최소 작업은 2 개 (삭제 XNUMX 개 및 대체 XNUMX 개)입니다.

우리는 하위 문제 즉, 문자열 X [0,…, i]를 Y [0,… j]로 변환하는 데 필요한 최소 연산 수를 찾아서이 문제를 해결할 수 있습니다.

단계

  1. X와 Y의 마지막 문자가 같으면 문자열 X [0,…, n-1]을 Y [0,…, m-1]로 변환하는 데 필요한 최소 연산을 찾습니다.
  2. X와 Y의 마지막 문자가 동일하지 않으면 세 가지 작업 중 하나를 수행 할 수 있습니다.
    • X의 마지막 색인에 삽입.
    • X의 마지막 인덱스 삭제.
    • X의 마지막 인덱스를 대체합니다.

위의 단계를 사용하여이 예제에 대한 재귀 트리를 그려 보겠습니다.

문자열 X = "ab"및 Y = "xy"따라서 n = 2 및 m = 2 ed (i, j)는 X [1,…, i에서 문자열 Y [1,…, j]를 얻는 데 필요한 최소 연산을 나타냅니다. ]. (1 기반 색인).

X의 어떤 문자도 Y와 같지 않으므로 모든 반복에서 허용되는 세 가지 작업 중 하나를 적용하여 재귀를 세 번 호출합니다.

거리 수정

우리가 볼 수 있듯이 위의 재귀에는이 절차의 최악의 복잡성이 O (3 ^ n) 인 많은 중첩 하위 문제가 있습니다.

이것은 다음을 사용하여 쉽게 줄일 수 있습니다. 동적 프로그래밍 중복되는 하위 문제의 재 계산 문제를 해결할 것입니다.

동적 프로그래밍 접근법

기본 조건

  1. 길이가 n 인 문자열을 주어진 길이가 0 인 문자열로 변환하려면 n 개의 삭제 작업이 필요합니다.
  2. 길이가 0 인 문자열을 주어진 길이가 n 인 문자열로 변환하려면 n 개의 삽입 작업이 필요합니다.

모든 위치에서 우리는이 두 가지 상황을 마주 할 수 있습니다.

  1. 두 문자열의 마지막 문자가 동일한 경우. 이 경우 아무 작업도 할 필요가 없습니다.이 문제에 대한 답은 하위 문제인 editDistance (X [0,…, i-1], Y [0)와 동일하다고 간단히 말할 수 있습니다. ,…., j-1]).
  2. 마지막 문자가 동일하지 않은 경우 다음 작업 중 하나를 선택해야합니다.
    • 삽입: 이 경우 i 번째 위치에 Y [j] 문자를 삽입하고 editDistance (X [1,… .i], Y [0,…., j-0])의 답에 1을 더합니다. 이렇게함으로써 두 문자열의 마지막 문자가 동일하다는 것을 확인합니다.
    • 삭제: 이 경우 X의 i 번째 문자를 삭제하고 editDistance (X [1,…., i-0], Y [1,…, j])의 답에 0을 더합니다. 이렇게하면 X 문자열의 마지막 문자가 남습니다. 즉, 삭제가 수행됩니다.
    • 치환: 이 경우 X [i]를 Y [j]로 대체하고 editDistance (X [1,…, i-0], Y [1,…, j-0])의 답에 1을 더합니다. 이것은 두 문자열에서 동일한 마지막 문자를 갖는 것과 동일한 경우가됩니다.

따라서 최소 작업 수를 필요로하므로 최소 세 가지 작업을 수행합니다.

C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
int min(int a,int b,int c){
  return min(a,min(b,c));
}
int editDistance(string X,string Y){
  int n=X.length();
  int m=Y.length();
  int ed[n+1][m+1];

  // to convert a string into null string we need to perform 
  // deletion operation n number of times where n is length of the string
  for(int i=0;i<=n;i++){
    ed[i][0]=i;
  }

  // to convert a null string into the given string we need to perform 
  // insertion operation n number of times where n is length of the string
  for(int i=0;i<=m;i++){
    ed[0][i]=i;
  }

  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      if(X[i-1]==Y[j-1]){
        // no operation required
        ed[i][j] = ed[i-1][j-1];
      }
      else{
        // one of the three operation required
        ed[i][j] = 1+ min( ed[i-1][j],   //deletion
                                   ed[i][j-1],   //insertion
                                   ed[i-1][j-1] //substitution
                       );
      }
    }
  }
  return ed[n][m];
}

int main()
{
  string X,Y;
    cin>>X>>Y;
  int result = editDistance(X,Y);
    cout<<"Minimum operations required to convert string "<<X<<" into string "<<Y<<" is: ";
  cout<<result<<"\n";
  return 0;
}
programming
problem
Minimum operations required to convert string programming into string problem is: 7

JAVA 프로그램

import java.util.Scanner;
class Main { 
    static int min(int x, int y, int z) 
    { 
        return Math.min(x,Math.min(y,z));
    }
    static int editDistance(String X, String Y) 
    { 
        int n=X.length();
    	int m=Y.length();
    	int ed[][] = new int[n + 1][m + 1]; 
    
    	// to convert a string into null string we need to perform 
    	// deletion operation n number of times where n is length of the string
    	for(int i=0;i<=n;i++){
    		ed[i][0]=i;
    	}
    
    	// to convert a null string into the given string we need to perform 
    	// insertion operation n number of times where n is length of the string
    	for(int i=0;i<=m;i++){
    		ed[0][i]=i;
    	}
    
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			if(X.charAt(i - 1)==Y.charAt(j - 1)){
    				// no operation required
    				ed[i][j] = ed[i-1][j-1];
    			}
    			else{
    				// one of the three operation required
    				ed[i][j] = 1+ min( ed[i-1][j],     //deletion
                                       ed[i][j-1],    //insertion
                                       ed[i-1][j-1]  //substitution
    					             );
    			}
    		}
    	}
    	return ed[n][m];
    } 
  
    public static void main(String args[]) 
    { 
        String X ,Y;
        Scanner sc = new Scanner(System.in);
        X = sc.nextLine();
        Y = sc.nextLine();
        int result = editDistance(X,Y);
        System.out.println("Minimum operations required to convert string "+X+" into string "+Y+" is: "+result); 
    } 
}
codingAndChill
codeAndGrow
Minimum operations required to convert string codingAndChill into string codeAndGrow is: 8

복잡성 분석

시간 복잡도 : O (n * m)

여기서 n = 첫 번째 문자열의 길이

m = 두 번째 문자열의 길이

두 개의 중첩 루프를 사용하여 2D 행렬 (ed)을 채울 때.

참조

Translate »