تین سٹروں کا LCS (سب سے طویل کامن سبیکنس)


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایمیزون کوڈ نیشن Expedia گوگل Uber Zoho
متحرک پروگرامنگ سلک

"تین ڈوروں کا LCS (سب سے طویل عام مشترکہ)" مسئلہ یہ بتاتا ہے کہ آپ کو 3 تار ملتے ہیں۔ ان 3 ڈوروں کا سب سے طویل مشترکہ حصquہ تلاش کریں۔ ایل سی ایس وہ تار ہے جو 3 ڈوروں میں عام ہے اور 3 حروف میں سے ایک ہی ترتیب والے حروف سے بنا ہے۔

مثال کے طور پر

تین سٹروں کا LCS (سب سے طویل کامن سبیکنس)

"gxtxayb" 
"abgtab" 
"gyaytahjb"
Length of LCS: 4("gtab")

نقطہ نظر

مسئلہ ہمیں ان پٹ کے طور پر 3 تار دیتا ہے اور ان میں سے سب سے طویل مشترکہ حص .ہ تلاش کرنے کے لئے کہا جاتا ہے۔ ایک تقویت ایک تار ہے جسے چھوڑ دیا جاتا ہے جب ہم اصل سٹرنگ میں سے کچھ حرفوں کو حذف کردیتے ہیں۔ اس طرح ہمیں دیئے گئے 3 تاروں میں مشترکہ سبقت تلاش کرنے کی ضرورت ہے جس کی لمبائی زیادہ سے زیادہ ہے۔

مسئلے کے لئے بولی نقطہ نظر عام طور پر طویل ترین مشترکہ سبسینس مسئلہ سے ملتا جلتا ہے۔ ہم نے پہلے ہی سب سے طویل رابطے کے مسئلے پر تبادلہ خیال کیا ہے۔ لیکن ہم نے اس پر بھی تبادلہ خیال کیا کہ بولی نقطہ نظر کافی حد تک موثر نہیں ہے تاکہ مسئلہ کو وقت کی حدود میں حل کیا جاسکے۔ لہذا ، وقت کی حد سے تجاوز کیے بغیر مسئلے کو حل کرنا۔ ہم استعمال کریں گے متحرک پروگرامنگ سوال حل کرنے کے ل.۔ حالت ایل سی ایس کی طرح ہوگی۔ یہاں ہمارے پاس 2 ریاستیں ہوں گی جو 3 اسی سلسلے میں اشاریے کا حوالہ دیں گی۔ لہذا ہماری ڈی پی سرنی ایک 3D سرنی ہوگی ، جہاں ہم ان میں سے 3 میں سے کوئی بھی اشاریہ 0 رکھتے ہیں تو 3 جمع کرتے ہیں۔ اگر تمام 0 اشاریہ میں ہی کردار ہے تو ہم سب پروبیلم کے جواب میں 3 کا اضافہ کرتے ہیں۔ انڈیکس میں سے ہر ایک کی لمبائی 1 سے 0 کم ہے)۔ اگر دونوں میں سے کسی میں ایک ہی حرف نہیں ہے تو پھر ہم سب سے زیادہ مشکلات کو ذخیرہ کرتے ہیں جہاں ہر انڈیکس میں ایک ایک کرکے کمی واقع ہوتی ہے۔

ضابطے

C ++ کوڈ میں 3 تار کے LCS تلاش کریں

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  string x = "gxtxayb"; 
  string y = "abgtab"; 
  string z = "gyaytahjb"; 
  int n = x.length(), m = y.length(), l = z.length();
  
  int dp[n][m][l];
  memset(dp, 0, sizeof dp);
  for (int i=0; i<n; i++){ 
    for (int j=0; j<m; j++){ 
      for (int k=0; k<l; k++){
        if (x[i] == y[j] && x[i] == z[k])
          dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
        else
          dp[i][j][k] = max({i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0, k>0 ? dp[i][j][k-1] : 0}); 
      } 
    } 
  } 
  cout<<dp[n-1][m-1][l-1];
  return 0; 
}
4

جاوا کوڈ 3 تار کے LCS تلاش کرنے کے لئے

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String x = "gxtxayb"; 
    String y = "abgtab"; 
    String z = "gyaytahjb"; 
    int n = x.length(), m = y.length(), l = z.length();
    
    int dp[][][] = new int[n][m][l];
    for (int i=0; i<n; i++){ 
      for (int j=0; j<m; j++){ 
        for (int k=0; k<l; k++){
          dp[i][j][k] = 0;
          if (x.charAt(i) == y.charAt(j) && x.charAt(i) == z.charAt(k))
            dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
          else
            dp[i][j][k] = Math.max(Math.max(i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0), k>0 ? dp[i][j][k-1] : 0); 
        } 
      } 
    } 
    System.out.println(dp[n-1][m-1][l-1]);
  }
}
4

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N * M * K)، کیونکہ ہمیں لمبائی والے تمام 3 تاروں کو عبور کرنا ہے N, M، اور K. استعمال کرنے کی وجہ سے متحرک پروگرامنگ ہم کثیر تعداد میں وقتی پیچیدگی کو کم کرنے کے قابل ہیں۔

خلائی پیچیدگی

O (N * M * K)، کیوں کہ ہمیں ابتدائی دشواری کا جواب حاصل کرنے کے لئے نتیجہ کو چھوٹے ذیلی مسئلہ کے ذخیرہ کرنے اور پھر نتیجہ کو یکجا کرنے کے لئے 3D ڈی ​​پی سرنی بنانا ہوگی۔ اس طرح تین تاروں کے LCS (طویل ترین مشترکہ سبسکوینس) کو تلاش کرنے میں کثیر الخلاقی پیچیدگی ہے۔