LCS (तीनवटा स्ट्रिंगको सब भन्दा लामो सामान्य उप-अनुक्रम)  


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन CodeNation Expedia गुगल Uber Zoho
डायनामिक प्रोग्रामिंग घागो

समस्या "LSS (तीनवटा स्ट्रिंगको सब भन्दा लामो आम उपक्रम)" तपाईंलाई 3 स्ट्रिंगहरू दिइन्छ भनेर बताउँछ। यी str स्ट्रि lonहरूको सब भन्दा लामो साधारण अनुभाग खोज्नुहोस्। LCS त्यो स्ट्रि that हो जुन among स्ट्रि among बीचमा समान हुन्छ र सबै given दिइएको स्ट्रि inमा समान क्रम भएको क्यारेक्टरहरूद्वारा बनेको हुन्छ।

उदाहरणका  

LCS (तीनवटा स्ट्रिंगको सब भन्दा लामो सामान्य उप-अनुक्रम)पिन

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

दृष्टिकोण  

समस्याले हामीलाई इनपुटको रूपमा str स्ट्रिंगहरू दिन्छ र यी मध्ये सब भन्दा लामो साधारण अनुभाग खोज्न भनियो। एक अनुक्रम एक स्ट्रिंग हो जुन छोडियो जब हामी मूल स्ट्रि fromबाट केहि वर्णहरू मेटाउँछौं। यसैले हामीले दिईएको str स्ट्रिंगहरुमा साधारण अनुक्रम खोज्नु पर्छ जुन अधिकतम लम्बाई छ।

समस्याको भोली दृष्टिकोण सामान्य सबैभन्दा लामो साधारण उप अनुक्रम समस्या जस्तै मिल्दोजुल्दो छ। हामीले पहिले नै लन्जेस्टकमोन उप-अनुक्रम समस्याको बारेमा छलफल गरिसकेका छौं। तर हामीले यो पनि छलफल ग .्यौं कि भोली दृष्टिकोण समयसीमा अन्तर्गत समस्या समाधान गर्न पर्याप्त कुशल छैन। त्यसो भए, समय सीमा नाघी समस्या समाधान गर्न। हामी प्रयोग गर्दछौं गतिशील प्रोग्रामिंग प्रश्न समाधान गर्नका लागि। अवस्था २ स्ट्रिंगहरूको लागि LCS जस्तै हुनेछ। यहाँ हामीसँग states राज्यहरू छन् जसले correspond सम्बद्ध स्ट्रिंगमा सूचका to्कलाई जनाउँछ। त्यसो भए हाम्रो डीपी एर्रे एक थ्रीडी एर्रे हुनेछ, जहाँ हामी ० भण्डार गर्छौं यदि ती मध्ये the मध्ये कुनै पनि सूचकांक ० छ भने, यदि सबै ind सूचकांकमा क्यारेक्टर छ भने हामी उपप्रब्ब्लमको लागि उत्तरमा १ थप्छौं (उपस्ट्रि Lको एलसीएसबाट लम्बाई ० देखि १ सूचकांकहरू भन्दा कम)। यदि कुनै पनि दुई स्ट्रिंगमा एक समान वर्ण छैन भने हामी सब-प्रोब्ब्लमहरूको अधिकतम भण्डार गर्दछौं जहाँ अनुक्रमणिका प्रत्येक एक एक गरी घट्छ।

पनि हेर्नुहोस्
एर्रेमा दायराहरूको उत्पादन

कोड  

C ++ कोड str तारको 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), किनकि हामीले लम्बाइ भएको सबै str तार पार गर्नुपर्नेछ N, M, र K। प्रयोग गरेको कारण डायनामिक प्रोग्रामिंग हामी बहुपक्षीयको घातीय समय जटिलता कम गर्न सक्षम छौं।

ठाउँ जटिलता

O (N * M * K), किनभने हामीले थोरै सबप्रोब्लमको लागि परिणाम भण्डारण गर्न र त्यसपछि सुरुको समस्याको लागि उत्तर प्राप्त गर्न परिणाम संयोजनको लागि थ्रीडी डीपी एर्रे सिर्जना गर्नुपर्नेछ। यसैले तीन स्ट्रिंगको LCS (सबै भन्दा लामो साधारण उपवाह) फेला पार्नाले बहुपक्षीय अन्तरिक्ष जटिलता छ।