مفاصلو


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Amazon ByteDance ڪريو گوگل Microsoft جي پلاٽينر ٽيڪنالاجيون چورس
متحرڪ پروگرامنگ اسٽرنگ

تبديلي واري مسئلي جي مسئلي ۾ اسان کي تبديلي لاءِ گهٽ ۾ گهٽ آپريشن ڳولڻ گهرجن جملو ڊيگهه جي X کان ٻئي ڪنڊي جي Y کان ڊيگهه جي م.

آپريشن جي اجازت آھي

  1. داخل ٿيل
  2. خارج ٿيڻ
  3. جزا

مفاصلو

مثال

انٽرويو

اسٽرنگ 1 = "اي بي سي ڊي"

اسٽرنگ 2 = "اي بي"

پيداوار:

گھٽ ۾ گھٽ آپريشن جي ضرورت آھي 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) ھڪڙي اسٽرنگ Y [1 ،…، j] حاصل ڪرڻ لاءِ گھربل گھٽين کي ظاھر ڪندو آھي [1 ،… ، مان ]. (1-بنياد وارو انڊيڪس).

جيئن ايڪس ايڪس ۾ ڪوبه ڪردار ساڳيو ئي ساڳيو يو وانگر ناهي ، ان ڪري هر تعصب تي ، اسين ٽن اجازت وارن عملن مان هڪ کي ٽي ڀيرا چوپائي سڏينداسين.

مفاصلو

جئين اسان ڏسي سگهون ٿا ته مٿي بيان ڪيل گھڻن مسئلن جي مٿان چڙ ڏياريندڙ سبب آهن ، جنهن جي ڪري هن طريقي جي بدترين پيچيدگي پيچيده O (3 ^ n) آهي.

انهي کي استعمال ڪندي آسانيءَ سان گهٽائي سگهجي ٿو متحرڪ پروگرامنگ جيڪا وڌيڪ حل ڪندڙ ذيلي مسئلن جي ٻيهر ڳڻتي جو مسئلو حل ڪندي.

متحرڪ پروگرامنگ جو طريقيڪار

بنيادي حالتون

  1. ڊيگهه جي ڊيگهه واري اسٽرنگ کي ڊيگهه واري ڊيگهه ۾ تبديل ڪرڻ لاءِ 0 ، اسان کي ڊي خارج ڪرڻ جا عمل گهرجن.
  2. ڊگھائي جي ھڪڙي تار کي 0 جي ھڪڙي تار کي تبديل ڪرڻ لاءِ ، اسان کي اين ڪنيڪشن آپريشنز جي ضرورت آھي.

هر پوزيشن تي اسين شايد انهن ٻن حالتن مان ڪو اچي سگهون ٿا

  1. جيڪڏھن ٻنھيءَ جو آخري ڪردار ساڳيو آھي. انهي صورت ۾ ، اسان کي ڪو آپريشن ڪرڻ جي ضرورت نه آهي ، اسان بس اهو چئي سگهون ٿا ته هن مسئلي جو جواب ساڳيو ئي هوندو مسئلي ذيلي مسئلي ايڊٽ جي فاصلو (X [0،…، i-1]، Y [0 ،…. ، j-1]).
  2. جيڪڏهن آخري ڪردار ساڳيو نه آهي ، اسان کي انهن مان هڪ کي چونڊڻ گهرجي.
    • داخل ٿيل: انهي صورت ۾ ، اسين Y [j] ڪردار کي ith پوزيشن تي داخل ڪنداسين ۽ 1 کي ايڊٽ جي فاصلو جي جواب ۾ شامل ڪنداسين (X [0،… .i]، Y [0،….، j-1]). ائين ڪرڻ سان اسان انهي ڳالهه کي يقيني بڻايون ته هاڻي ٻنهي قوتن جو آخري ڪردار ساڳيو آهي.
    • خارج ڪريو انهي صورت ۾ ، اسان ايڪس جي ايٿ ڪردار کي خارج ڪنداسين ۽ 1 کي ايڊٽ جي فاصلو جي جواب ۾ شامل ڪنداسين (X [0 ،…. ، i-1] ، Y [0 ،… ، j]). ايئن ڪرڻ سان اسان ايڪس اسٽرنگ جو آخري ڪردار ڇڏي رهيا آهيون ، يعني خارج ڪرڻ وارو ڪم ڪيو ويندو آهي.
    • جزا ان صورت ۾ اسان ايڪس [I] کي Y [j] سان تبديل ڪنداسين ۽ 1 کي ايڊٽ جي ايڊٽ جي جواب ۾ شامل ڪنداسين (X [0،…، i-1]، Y [0،…، j-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

پيچيدگي تجزيي

وقت جي پيچيدگي: اي (ن * م)

جتي n = پهرين تار جي ڊيگهه

م = ٻئي تار جي ڊيگهه

جئين اسان ٻه ڊيزائين لوپ استعمال ڪندي هڪ 2D ميٽرڪس ڀرجي رهيا آهيون.

حوالا