LCS (המשך הנפוץ הארוך ביותר) של שלושה מיתרים


רמת קושי קשה
נשאל לעתים קרובות אמזון בעברית CodeNation Expedia Google סופר Zoho
תכנות דינמי מחרוזת

הבעיה "LCS (המשך הנפוץ הארוך ביותר) של שלוש מחרוזות" קובעת שקיבלתם 3 מחרוזות. גלה את המשך הנפוץ הארוך ביותר של שלושת המיתרים הללו. LCS הוא המחרוזת הנפוצה בין שלושת המיתרים ועשויה מדמויות בעלות סדר זהה בכל שלושת המיתרים הנתונים.

דוגמה

LCS (המשך הנפוץ הארוך ביותר) של שלושה מיתרים

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

גישה

הבעיה נותנת לנו 3 מחרוזות כקלט וביקשה למצוא את ההמשך הנפוץ הארוך ביותר מבין אלה. המשך הוא מחרוזת שנותרה כאשר אנו מוחקים חלק מהתווים מהמחרוזת המקורית. לפיכך עלינו למצוא את ההמשכיות הנפוצה בשלושת המיתרים הנתונים שיש להם את האורך המרבי.

הגישה הנאיבית לבעיה דומה למדי לזו של בעיית ההמשך הנפוץ הארוך ביותר. כבר דנו בבעיית ההמשך של LongestCommon. אך דנו גם כי הגישה הנאיבית אינה יעילה מספיק בכדי לפתור את הבעיה במגבלות הזמן. לכן, כדי לפתור את הבעיה מבלי לחרוג ממגבלת הזמן. אנחנו נשתמש תכנות דינמי לפתרון השאלה. התנאי יהיה דומה לזה של LCS עבור 2 מיתרים. כאן יהיו לנו 3 מצבים אשר יתייחסו למדדים בשלושת המיתרים המתאימים. אז מערך ה- dp שלנו יהיה מערך תלת-ממדי, בו אנו מאחסנים 3 אם אחד מהמדדים מבין 3 מהם הוא 0. אם התו בכל 3 המדדים הוא, נוסיף 0 לתשובה עבור תת-הבעיה (LCS של משטחים מ- אורך 3 עד 1 פחות מכל אחד מהמדדים). אם לאחת משתי המחרוזות אין אותו תו, אנו שומרים את מקסימום תת-הבעיות בהן מקטינים כל אחד מהאינדקס בזה אחר זה.

קופונים

קוד C ++ למציאת LCS של 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

קוד Java למציאת LCS של 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

ניתוח מורכבות

מורכבות זמן

O (N * M * K), כי עלינו לחצות את כל שלושת המיתרים שיש להם אורך N, M, ו K. בגלל השימוש תכנות דינמי אנו מסוגלים להפחית את מורכבות הזמן האקספוננציאלית לפולינום.

מורכבות בחלל

O (N * M * K), מכיוון שעלינו ליצור מערך DP 3D לאחסון התוצאה עבור תת-בעיה קטנה יותר ואז שילוב התוצאה כדי לקבל את התשובה לבעיה הראשונית. לפיכך למציאת ה- LCS (המשך הנפוץ הארוך ביותר) של שלושה מיתרים יש מורכבות מרחב פולינומית.