ಮೂರು ತಂತಿಗಳ ಎಲ್ಸಿಎಸ್ (ಉದ್ದವಾದ ಸಾಮಾನ್ಯ ಪರಿಣಾಮ)


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಕೋಡ್‌ನೇಷನ್ Expedia ಗೂಗಲ್ ಉಬರ್ ಜೊಹೊ
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಸ್ಟ್ರಿಂಗ್

"ಮೂರು ತಂತಿಗಳ ಎಲ್ಸಿಎಸ್ (ಉದ್ದವಾದ ಸಾಮಾನ್ಯ ಪರಿಣಾಮ)" ಸಮಸ್ಯೆ ನಿಮಗೆ 3 ತಂತಿಗಳನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಈ 3 ತಂತಿಗಳ ಉದ್ದದ ಸಾಮಾನ್ಯ ಅನುಕ್ರಮವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ. ಎಲ್ಸಿಎಸ್ ಎನ್ನುವುದು 3 ತಂತಿಗಳಲ್ಲಿ ಸಾಮಾನ್ಯವಾಗಿದೆ ಮತ್ತು ಕೊಟ್ಟಿರುವ 3 ತಂತಿಗಳಲ್ಲಿ ಒಂದೇ ಕ್ರಮವನ್ನು ಹೊಂದಿರುವ ಅಕ್ಷರಗಳಿಂದ ಮಾಡಲ್ಪಟ್ಟಿದೆ.

ಉದಾಹರಣೆ

ಮೂರು ತಂತಿಗಳ ಎಲ್ಸಿಎಸ್ (ಉದ್ದವಾದ ಸಾಮಾನ್ಯ ಪರಿಣಾಮ)

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

ಅಪ್ರೋಚ್

ಸಮಸ್ಯೆಯು ನಮಗೆ 3 ತಂತಿಗಳನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ನೀಡುತ್ತದೆ ಮತ್ತು ಇವುಗಳಲ್ಲಿ ದೀರ್ಘವಾದ ಸಾಮಾನ್ಯ ಅನುಸರಣೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳಿದೆ. ನಂತರದ ಸ್ಟ್ರಿಂಗ್ ನಾವು ಮೂಲ ಸ್ಟ್ರಿಂಗ್‌ನಿಂದ ಕೆಲವು ಅಕ್ಷರಗಳನ್ನು ಅಳಿಸಿದಾಗ ಉಳಿದಿರುವ ಸ್ಟ್ರಿಂಗ್ ಆಗಿದೆ. ಆದ್ದರಿಂದ ನಾವು ಗರಿಷ್ಠ ಉದ್ದವನ್ನು ಹೊಂದಿರುವ 3 ತಂತಿಗಳಲ್ಲಿ ಸಾಮಾನ್ಯ ಅನುಸರಣೆಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.

ಸಮಸ್ಯೆಯ ನಿಷ್ಕಪಟ ವಿಧಾನವು ಸಾಮಾನ್ಯ ಉದ್ದದ ಸಾಮಾನ್ಯ ನಂತರದ ಸಮಸ್ಯೆಗೆ ಹೋಲುತ್ತದೆ. ನಾವು ಈಗಾಗಲೇ ಲಾಂಗೆಸ್ಟ್ ಕಾಮನ್ ನಂತರದ ಸಮಸ್ಯೆಯನ್ನು ಚರ್ಚಿಸಿದ್ದೇವೆ. ಆದರೆ ಸಮಯದ ಮಿತಿಯಲ್ಲಿ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ನಿಷ್ಕಪಟ ವಿಧಾನವು ಸಾಕಷ್ಟು ಪರಿಣಾಮಕಾರಿಯಾಗಿಲ್ಲ ಎಂದು ನಾವು ಚರ್ಚಿಸಿದ್ದೇವೆ. ಆದ್ದರಿಂದ, ಸಮಯದ ಮಿತಿಯನ್ನು ಮೀರದಂತೆ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು. ನಾವು ಬಳಸುತ್ತೇವೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಪ್ರಶ್ನೆಯನ್ನು ಪರಿಹರಿಸಲು. ಈ ಸ್ಥಿತಿಯು 2 ತಂತಿಗಳಿಗೆ ಎಲ್ಸಿಎಸ್ನಂತೆಯೇ ಇರುತ್ತದೆ. ಇಲ್ಲಿ ನಾವು 3 ರಾಜ್ಯಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ ಅದು 3 ಅನುಗುಣವಾದ ತಂತಿಗಳಲ್ಲಿ ಸೂಚ್ಯಂಕಗಳನ್ನು ಉಲ್ಲೇಖಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ ನಮ್ಮ ಡಿಪಿ ಅರೇ 3 ಡಿ ಅರೇ ಆಗಿರುತ್ತದೆ, ಅವುಗಳಲ್ಲಿ 0 ರಲ್ಲಿನ ಯಾವುದೇ ಸೂಚ್ಯಂಕಗಳು 3 ಆಗಿದ್ದರೆ ನಾವು 0 ಅನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಎಲ್ಲಾ 3 ಸೂಚ್ಯಂಕಗಳಲ್ಲಿನ ಅಕ್ಷರಗಳಿದ್ದರೆ ನಾವು ಸಬ್‌ಪ್ರೊಬ್ಲೆಮ್‌ಗೆ ಉತ್ತರಕ್ಕೆ 1 ಅನ್ನು ಸೇರಿಸುತ್ತೇವೆ (ಎಲ್‌ಸಿಎಸ್ ಸಬ್‌ಸ್ಟ್ರಿಂಗ್‌ಗಳು ಪ್ರತಿಯೊಂದು ಸೂಚ್ಯಂಕಗಳಿಗಿಂತ ಉದ್ದ 0 ರಿಂದ 1 ಕಡಿಮೆ). ಎರಡು ತಂತಿಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಒಂದೇ ಅಕ್ಷರವಿಲ್ಲದಿದ್ದರೆ ನಾವು ಗರಿಷ್ಠ ಉಪ-ಸಮಸ್ಯೆಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ, ಅಲ್ಲಿ ಪ್ರತಿಯೊಂದು ಸೂಚ್ಯಂಕವನ್ನು ಒಂದೊಂದಾಗಿ ಇಳಿಸಬಹುದು.

ಕೋಡ್

3 ತಂತಿಗಳ ಎಲ್ಸಿಎಸ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#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 ತಂತಿಗಳ ಎಲ್ಸಿಎಸ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ * ಕೆ), ಏಕೆಂದರೆ ನಾವು ಉದ್ದವನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ 3 ತಂತಿಗಳನ್ನು ಹಾದುಹೋಗಬೇಕು N, M, ಮತ್ತು K. ಬಳಸುವುದರಿಂದ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಘಾತೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಬಹುಪದಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಲು ನಮಗೆ ಸಾಧ್ಯವಾಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ * ಕೆ), ಏಕೆಂದರೆ ಸಣ್ಣ ಸಬ್‌ಪ್ರೊಬ್ಲೆಮ್‌ಗಾಗಿ ಫಲಿತಾಂಶವನ್ನು ಸಂಗ್ರಹಿಸಲು ಮತ್ತು ನಂತರ ಆರಂಭಿಕ ಸಮಸ್ಯೆಗೆ ಉತ್ತರವನ್ನು ಪಡೆಯಲು ಫಲಿತಾಂಶವನ್ನು ಸಂಯೋಜಿಸಲು ನಾವು 3D ಡಿಪಿ ರಚನೆಯನ್ನು ರಚಿಸಬೇಕಾಗಿದೆ. ಹೀಗೆ ಮೂರು ತಂತಿಗಳ ಎಲ್ಸಿಎಸ್ (ಉದ್ದದ ಸಾಮಾನ್ಯ ಪರಿಣಾಮ) ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಬಹುಪದೀಯ ಜಾಗದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ.