Қашықтықты өңдеу


Күрделілік дәрежесі қиын
Жиі кіреді Amazon ByteDance Facebook Google Microsoft Palantir Technologies шаршы
Динамикалық бағдарламалау String

Қашықтықты өңдеу мәселесінде а-ны түрлендіруге қажетті минималды амалдар санын табу керек жол Ұзындықтың X ұзындығының m басқа Y жолына дейін.

Рұқсат етілген операциялар:

  1. енгізу
  2. жою
  3. Ауыстыру

Қашықтықты өңдеу

мысал

Кіру:

String1 = “abcd”

String2 = “abe”

Шығару:

Қажетті минималды операциялар - 2 (бір жою және бір ауыстыру)

Біз бұл сұрақты оның ішкі мәселесін шешу арқылы шеше аламыз, яғни X [0,…, i] жолын Y [0,… j] -ге түрлендіру үшін қажетті минималды амалдарды табу керек.

қадамдары

  1. Егер X және Y соңғы символдары бірдей болса, онда X [0,…, n-1] жолын Y [0,…, m-1] түрлендіруге қажетті минималды амалдарды табыңыз.
  2. Егер X және Y соңғы таңбалары бірдей болмаса, онда біз үш амалдың бірін жасай аламыз:
    • Х индексінің соңғы индексі бойынша енгізу.
    • Х-тің соңғы индексін жою.
    • Х-тің соңғы индексін ауыстыру.

Жоғарыда көрсетілген қадамдарды қолданып, келесі мысалға рекурсия ағашын салуға тырысайық:

жол X = “ab” және Y = “xy” Сондықтан n = 2 және m = 2 ed (i, j) X [1,…, i ішінен Y [1,…, j] жолын алу үшін қажетті минималды амалдарды білдіреді. ]. (1 негізделген индекс).

Х-тегі таңбалардың ешқайсысы Y-мен бірдей емес болғандықтан, әр қайталану кезінде біз үш амалдың біреуін қолдану арқылы рекурсияны үш рет шақырамыз.

Қашықтықты өңдеу

Көріп отырғанымыздай, жоғарыдағы рекурсияда көптеген қайталанатын ішкі проблемалар бар, осыған байланысты бұл процедураның ең нашар күрделілігі O (3 ^ n) болып табылады.

Мұны пайдаланып оңай азайтуға болады Динамикалық бағдарламалау бұл қайталанатын ішкі мәселелерді қайта есептеу мәселесін шешеді.

Бағдарламалаудың динамикалық тәсілі

Негізгі шарттар

  1. Ұзындығы n жолын берілген 0 ұзындығына ауыстыру үшін n жою операциясын қажет етеміз.
  2. Ұзындығы 0 жолын берілген ұзындық n жолына түрлендіру үшін n кірістіру операциясын қажет етеміз.

Кез-келген позицияда біз осы екі жағдайдың кез-келгеніне кезігуіміз мүмкін

  1. Егер екі жолдың да соңғы таңбасы бірдей болса. Бұл жағдайда біз ешқандай операция жасаудың қажеті жоқ, бұл жайттың жауабы editDistance (X [0,…, i-1], Y [0) қосалқы есептерімен бірдей болады деп айтуға болады. ,…., J-1]).
  2. Егер соңғы таңба бірдей болмаса, біз келесі амалдардың бірін таңдауымыз керек:
    • енгізу: Бұл жағдайда Y [j] таңбасын ith позициясына енгіземіз және editDistance (X [1,… .i], Y [0,…., J-0]) жауабына 1 қосамыз. Осылай жасай отырып, біз қазір екі жолдың да соңғы таңбасының бірдей болуын қамтамасыз етеміз.
    • Жою: Бұл жағдайда біз X таңбасын жоямыз және editDistance жауабына 1 қосамыз (X [0,…., I-1], Y [0,…, j]). Осылайша біз 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 = 1-жолдың ұзындығы

m = 2-жолдың ұзындығы

өйткені біз екі кірістірілген ілмектерді пайдаланып 2D матрицасын (ed) толтырамыз.

Әдебиеттер тізімі