तीन तार के LCS (सबसे लंबे समय तक सामान्य उपसर्ग)


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना कोडेशन Expedia गूगल Uber Zoho
गतिशील प्रोग्रामिंग तार

समस्या "LCS (तीन बार के सबसे लंबे समय तक सामान्य परिणाम)" में कहा गया है कि आपको 3 तार दिए गए हैं। इन 3 स्ट्रिंग्स के सबसे लंबे सामान्य परिणाम का पता लगाएं। LCS वह स्ट्रिंग है जो 3 स्ट्रिंग्स के बीच आम है और 3 दिए गए स्ट्रिंग्स में से सभी में समान क्रम वाले वर्णों से बना है।

उदाहरण

तीन तार के LCS (सबसे लंबे समय तक सामान्य उपसर्ग)

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

दृष्टिकोण

समस्या हमें इनपुट के रूप में 3 तार देती है और इनमें से सबसे लंबे समय तक सामान्य परिणाम खोजने के लिए कहा गया है। एक अनुवर्ती एक स्ट्रिंग है जिसे तब छोड़ा जाता है जब हम कुछ पात्रों को मूल स्ट्रिंग से हटाते हैं। इस प्रकार हमें दी गई 3 स्ट्रिंग्स में आम परवर्ती को खोजने की आवश्यकता है जिसकी अधिकतम लंबाई है।

समस्या के लिए भोली दृष्टिकोण सामान्य लॉन्गेस्ट कॉमन सबडरेन्स समस्या के समान है। हमने पहले ही LongestCommon Subfterence समस्या पर चर्चा की थी। लेकिन हमने यह भी चर्चा की कि समय सीमा के तहत समस्या को हल करने के लिए भोली दृष्टिकोण पर्याप्त कुशल नहीं है। तो, समय सीमा को पार किए बिना समस्या को हल करने के लिए। हम इस्तेमाल करेंगे गतिशील प्रोग्रामिंग प्रश्न हल करने के लिए। स्थिति 2 स्ट्रिंग्स के लिए एलसीएस के समान होगी। यहां हमारे पास 3 राज्य होंगे जो 3 संबंधित स्ट्रिंग्स में सूचकांकों को संदर्भित करेंगे। तो हमारा डीपी एरे 3 डी ऐरे होगा, जहां हम 0 स्टोर करते हैं यदि उनमें से 3 में से कोई भी इंडेक्स 0. है। यदि सभी 3 इंडेक्स पर वर्ण है तो हम सबप्रोमल (सब्सट्रेट के एलसीएस) के उत्तर में 1 जोड़ते हैं। लंबाई प्रत्येक सूचकांक से 0 से 1 कम)। यदि दोनों में से किसी एक तार में समान वर्ण नहीं है, तो हम अधिकतम उपप्रक्रमों को संग्रहीत करते हैं, जहाँ एक-एक करके सूचकांक में से प्रत्येक को घटाते हैं।

कोड

3 तार के LCS खोजने के लिए C ++ कोड

#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 DP सरणी बनाना है और फिर प्रारंभिक समस्या के लिए उत्तर प्राप्त करने के लिए परिणाम का संयोजन करना है। इस प्रकार तीन तार के LCS (सबसे लंबे समय तक सामान्य उपसर्ग) को खोजने में बहुपद स्थान की जटिलता है।