거리 수정

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

편집 거리 문제에서 우리는 변환에 필요한 최소 작업 수를 찾아야합니다. 길이가 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 »