فاصلہ ترمیم کریں


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایمیزون ByteDance فیس بک گوگل مائیکروسافٹ پالنر ٹیکنالوجیز چوک
متحرک پروگرامنگ سلک

ترمیم کے فاصلہ کے مسئلے میں ہمیں کم سے کم تعداد میں کام کرنا ضروری ہے جس میں تبدیل ہونا ضروری ہے سٹرنگ لمبائی کا X اور لمبائی کا ایک اور تار Y

آپریشنز کی اجازت:

  1. اندراج
  2. منسوخی
  3. متبادل

فاصلہ ترمیم کریں

مثال کے طور پر

ان پٹ:

سٹرنگ 1 = "abcd"

سٹرنگ 2 = "ابی"

: پیداوار

کم از کم کارروائیوں کی ضرورت 2 ہے (ایک حذف اور ایک متبادل)

ہم اس سوال کو اس کے ذیلی مسئلے کو حل کرکے حل کرسکتے ہیں ، یعنی اسٹرنگ X [0،…، i] میں Y [0،… j] میں تبدیل کرنے کے لئے مطلوبہ کم سے کم آپریشنز کی تلاش کریں۔

مراحل

  1. اگر X اور Y کا آخری حرف ایک ہی ہے ، تو اسٹرنگ X [0،…، n-1] کو Y [0،…، m-1] میں تبدیل کرنے کے لئے مطلوبہ کم سے کم آپریشنز تلاش کریں۔
  2. اگر X اور Y کا آخری کردار ایک جیسے نہیں ہیں ، تو ہم تینوں میں سے ایک کام کر سکتے ہیں۔
    • ایکس کے آخری انڈیکس میں اندراج۔
    • ایکس کا آخری انڈیکس کا خاتمہ۔
    • ایکس کے آخری انڈیکس کی جگہ لے لے۔

مندرجہ بالا اقدامات کا استعمال کرتے ہوئے ، آئیے اس مثال کے لئے تکرار کے درخت کو اپنی طرف متوجہ کرنے کی کوشش کریں:

سٹرنگ X = "اب" اور وائی = "xy" لہذا n = 2 اور ایم = 2 ایڈ (i ، j) X [1،…، j] سے سٹرنگ Y [1،…، j] حاصل کرنے کے لئے درکار کم سے کم کارروائیوں کی نشاندہی کرتا ہے۔ ]. (1 پر مبنی انڈیکس)

چونکہ X میں سے کوئی بھی حرف Y کی طرح نہیں ہے ، لہذا ہر تکرار پر ، ہم تینوں اجازت دہندائی کارروائیوں میں سے ایک کا اطلاق کرکے تین بار تکرار کریں گے۔

فاصلہ ترمیم کریں

جیسا کہ ہم دیکھ سکتے ہیں کہ مذکورہ بالا تکرار میں بہت سارے اوورلپنگ ذیلی دشواری موجود ہیں جس کی وجہ سے اس طریقہ کار کی بدترین صورت پیچیدگی O (3 ^ n) ہے۔

اس کو استعمال کرکے آسانی سے کم کیا جاسکتا ہے متحرک پروگرامنگ جو اوورلیپنگ سب پریشانیوں کی دوبارہ گنتی کے معاملے کو حل کرے گا۔

متحرک پروگرامنگ نقطہ نظر

بنیادی شرائط

  1. لمبائی کے ایک تار کو دیئے گئے لمبائی 0 میں تبدیل کرنے کے ل we ، ہمیں n حذف کرنے کی کارروائیوں کی ضرورت ہے۔
  2. لمبائی کے ایک تار کو دیئے گئے لمبائی کی لمبائی میں تبدیل کرنے کے ل we ، ہمیں این داخل کرنے کی کارروائیوں کی ضرورت ہے۔

ہر پوزیشن پر ہم ان دو حالتوں میں سے کسی کو بھی دیکھ سکتے ہیں

  1. اگر دونوں تاروں کا آخری کردار ایک جیسا ہے۔ اس معاملے میں ، ہمیں کوئی آپریشن کرنے کی ضرورت نہیں ہے ، ہم صرف اتنا کہہ سکتے ہیں کہ اس مسئلے کا جواب وہی ہوگا جو سب پریشانی میں ترمیم فاصلہ (X [0،…، i-1]، Y [0] ،…. ، j-1])۔
  2. اگر آخری کردار ایک جیسا نہیں ہے تو ، ہمیں ان میں سے ایک کارروائی کا انتخاب کرنا ہوگا۔
    • اندراج: اس معاملے میں ، ہم Y [j] کردار کو ith پوزیشن پر داخل کریں گے اور ترمیم کے جواب میں 1 شامل کریں گے (X [0،… .i]، Y [0،….، j-1])۔ ایسا کرنے سے ہم یہ یقینی بناتے ہیں کہ اب دونوں تاروں کا آخری کردار ایک جیسے ہے۔
    • حذف کرنا: اس معاملے میں ، ہم X کے ith کردار کو حذف کردیں گے اور ترمیم کے فاصلے (X [1،….، i-0]، Y [1،…، j]) کے جواب میں 0 شامل کریں گے۔ ایسا کرنے سے ہم ایکس سٹرنگ کے آخری کردار کو چھوڑ رہے ہیں یعنی ، ڈیلیٹ کرنے کا کام انجام دیا گیا ہے۔
    • متبادل: اس معاملے میں ہم X [i] کو Y [j] کا متبادل بنائیں گے اور ترمیم کے فاصلے (X [1،…، i-0]، Y [1،…، j-0]) میں 1 شامل کریں گے۔ یہ ایک ہی معاملہ بن جاتا ہے جیسے دونوں تاروں میں برابر کا آخری کردار ہونا۔

چونکہ ہمیں کم از کم آپریشنوں کی ضرورت ہوتی ہے ، لہذا ہم تینوں ممکنہ کاروائیوں میں سے کم از کم کام لیں گے۔

سی ++ پروگرام

#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

جاوا پروگرام

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 = پہلی تار کی لمبائی

میٹر = دوسری تار کی لمبائی

چونکہ ہم دو نیسڈ لوپس کا استعمال کرتے ہوئے 2D میٹرکس (ای ڈی) بھر رہے ہیں۔

حوالہ جات