మూడు తీగల యొక్క LCS (పొడవైన సాధారణ పరిణామం)


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది అమెజాన్ కోడ్‌నేషన్ Expedia ద్వారా గూగుల్ ఉబెర్ జోహో
డైనమిక్ ప్రోగ్రామింగ్ స్ట్రింగ్

“మూడు తీగల యొక్క LCS (పొడవైన సాధారణ పరిణామం)” సమస్య మీకు 3 తీగలను ఇచ్చిందని పేర్కొంది. ఈ 3 తీగల యొక్క పొడవైన సాధారణ తదుపరిదాన్ని కనుగొనండి. LCS అనేది 3 తీగలలో సాధారణం మరియు ఇచ్చిన 3 తీగలలో ఒకే క్రమాన్ని కలిగి ఉన్న అక్షరాలతో రూపొందించబడింది.

ఉదాహరణ

మూడు తీగల యొక్క LCS (పొడవైన సాధారణ పరిణామం)

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

అప్రోచ్

సమస్య మాకు 3 తీగలను ఇన్‌పుట్‌గా ఇస్తుంది మరియు వీటిలో ఎక్కువ కాలం సాధారణమైన తదుపరిదాన్ని కనుగొనమని కోరింది. తరువాతి స్ట్రింగ్ అనేది అసలు స్ట్రింగ్ నుండి కొన్ని అక్షరాలను మేము తొలగించినప్పుడు మిగిలి ఉంటుంది. అందువల్ల మనం ఇచ్చిన 3 తీగలలో గరిష్ట పొడవును కలిగి ఉన్న సాధారణ పరిణామాన్ని కనుగొనాలి.

సమస్యకు అమాయక విధానం సాధారణ పొడవైన సాధారణ తరువాతి సమస్యతో సమానంగా ఉంటుంది. మేము ఇప్పటికే లాంగెస్ట్ కామన్ తరువాత సమస్య గురించి చర్చించాము. కానీ సమయ పరిమితుల్లో సమస్యను పరిష్కరించడానికి అమాయక విధానం సమర్థవంతంగా లేదని మేము చర్చించాము. కాబట్టి, సమయ పరిమితిని మించకుండా సమస్యను పరిష్కరించడానికి. మేము ఉపయోగిస్తాము డైనమిక్ ప్రోగ్రామింగ్ ప్రశ్న పరిష్కరించడానికి. ఈ పరిస్థితి 2 తీగలకు LCS మాదిరిగానే ఉంటుంది. ఇక్కడ మనకు 3 రాష్ట్రాలు ఉంటాయి, ఇవి 3 సంబంధిత తీగలలో సూచికలను సూచిస్తాయి. కాబట్టి మన డిపి అర్రే 3 డి అర్రే అవుతుంది, ఇక్కడ 0 వాటిలో ఏదైనా సూచికలు 3 అయితే 0 ని నిల్వ చేస్తాము. మొత్తం 3 సూచికలలోని అక్షరం ఉంటే, అప్పుడు మేము సబ్‌ప్రోబ్లమ్ (ఎల్‌సిఎస్ ఆఫ్ సబ్‌స్ట్రింగ్స్ నుండి ప్రతి సూచికల కంటే పొడవు 1 నుండి 0 తక్కువ). రెండు తీగలలో దేనిలోనైనా ఒకే అక్షరం లేకపోతే, మేము గరిష్టంగా ఉపప్రాబ్లమ్‌లను నిల్వ చేస్తాము, ఇక్కడ ప్రతి సూచిక ఒక్కొక్కటిగా తగ్గుతుంది.

కోడ్

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 (పొడవైన సాధారణ పరిణామం) ను కనుగొనడం బహుపది స్థల సంక్లిష్టతను కలిగి ఉంటుంది.