නූල් තුනක LCS (දීර් est තම පොදු පසු විපරම)


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇමේසන් කෝඩ්නේෂන් Expedia ගූගල් Uber Zoho
ගතික වැඩසටහන්කරණය String

“නූල් තුනක LCS (දීර් est තම පොදු පසු විපරම)” ගැටලුවේ සඳහන් වන්නේ ඔබට නූල් 3 ක් ලබා දී ඇති බවයි. මෙම නූල් 3 හි දීර් est තම පොදු අනුක්‍රමය සොයා ගන්න. LCS යනු නූල් 3 අතර පොදු වන නූල වන අතර එය ලබා දී ඇති නූල් 3 න් එකම අනුපිළිවෙලක් ඇති අක්ෂර වලින් සෑදී ඇත.

උදාහරණයක්

නූල් තුනක LCS (දීර් est තම පොදු පසු විපරම)

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

ප්රවේශය

ගැටළුව අපට ආදාන ලෙස නූල් 3 ක් ලබා දෙන අතර, මේවායින් දීර් est තම පොදු පසු විපරම සොයා ගැනීමට ඉල්ලා සිටියේය. පසු විපරමක් යනු මුල් අක්ෂරයෙන් අපි සමහර අක්ෂර මකා දැමූ විට ඉතිරි වන නූලකි. මේ අනුව, ලබා දී ඇති නූල් 3 හි උපරිම දිග ඇති පොදු පසු විපරම සොයාගත යුතුය.

ගැටලුවට බොළඳ ප්‍රවේශය සාමාන්‍ය දිගම පොදු පසු විපරම් ගැටලුවට බෙහෙවින් සමාන ය. අපි දැනටමත් දීර් est තම පොදු පසු විපරම් ගැටලුව ගැන සාකච්ඡා කර ඇත්තෙමු. නමුත් කාල සීමාවන් යටතේ ගැටළුව විසඳීමට තරම් බොළඳ ප්‍රවේශය කාර්යක්ෂම නොවන බව ද අපි සාකච්ඡා කළෙමු. එබැවින්, කාල සීමාව ඉක්මවා නොයා ගැටළුව විසඳීමට. අපි භාවිතා කරමු ගතික වැඩසටහන්කරණය ප්‍රශ්නය විසඳීම සඳහා. මෙම තත්ත්වය නූල් 2 ක් සඳහා LCS තත්වයට සමාන වේ. මෙහිදී අපට ප්‍රාන්ත 3 ක් ඇති අතර එය අනුරූප නූල් 3 හි දර්ශක වෙත යොමු වේ. එබැවින් අපගේ ඩීපී අරාව ත්‍රිමාණ අරාවක් වනු ඇත, එහිදී ඒවා 3 න් ඕනෑම දර්ශකයක් 0 නම් අපි 3 ගබඩා කරමු. සියලු දර්ශක 0 හි ඇති අක්‍ෂරය නම් අපි උපප්‍රශ්නය සඳහා පිළිතුරට 3 ක් එකතු කරමු (LCS උපස්ථර වලින් එක් එක් දර්ශකවලට වඩා දිග 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් * එම් * කේ), මොකද අපි දිගින් යුත් නූල් තුනම ගමන් කළ යුතුයි N, M, සහ K. භාවිතා කිරීම නිසා ගතික වැඩසටහන්කරණය On ාතීය කාල සංකීර්ණතාව බහුපදයට අඩු කිරීමට අපට හැකියාව ඇත.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එන් * එම් * කේ), මන්ද යත්, කුඩා උපප්‍රශ්නය සඳහා ප්‍රති result ලය ගබඩා කිරීම සඳහා ත්‍රිමාණ ඩීපී අරා නිර්මාණය කළ යුතු අතර ආරම්භක ගැටළුවට පිළිතුර ලබා ගැනීම සඳහා ප්‍රති result ලය ඒකාබද්ධ කිරීමයි. මේ අනුව නූල් තුනක LCS (දිගම පොදු පසු විපරම) සොයා ගැනීම බහුපද අවකාශයේ සංකීර්ණතාවයක් ඇත.