LCS (ຜົນກະທົບຕໍ່ທີ່ຍາວທີ່ສຸດ) ຂອງສາມສາຍ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon CodeNation Expedia ກູໂກ Uber Zoho
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ string

ບັນຫາ“ LCS (ຜົນສະທ້ອນທີ່ຍາວນານທີ່ສຸດທີ່ຍາວນານ) ຂອງສາມເຊືອກ” ລະບຸວ່າທ່ານໄດ້ຮັບ 3 ເຊືອກ. ຊອກຫາ 3 ສາຍຕໍ່ໄປທີ່ພົບເລື້ອຍທີ່ສຸດທີ່ຍາວທີ່ສຸດ. LCS ແມ່ນສາຍທີ່ມີຢູ່ທົ່ວໄປໃນ 3 ສາຍແລະຖືກສ້າງຂຶ້ນຈາກຕົວອັກສອນທີ່ມີລະບຽບຮຽບຮ້ອຍຄືກັນກັບທັງ ໝົດ 3 ສາຍທີ່ໃຫ້.

ຍົກຕົວຢ່າງ

LCS (ຜົນກະທົບຕໍ່ທີ່ຍາວທີ່ສຸດ) ຂອງສາມສາຍ

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

ວິທີການ

ບັນຫາດັ່ງກ່າວເຮັດໃຫ້ພວກເຮົາມີ 3 ເສັ້ນຄືການປ້ອນຂໍ້ມູນແລະໄດ້ຂໍໃຫ້ຊອກຫາການຕິດຕໍ່ກັນທີ່ຍາວທີ່ສຸດໃນບັນດາສິ່ງເຫລົ່ານີ້. ຕົວຢ່າງຕໍ່ມາແມ່ນສາຍເຊືອກທີ່ຖືກປະໄວ້ໃນເວລາທີ່ພວກເຮົາລຶບບາງຕົວອັກສອນອອກຈາກສາຍຕົ້ນສະບັບ. ດັ່ງນັ້ນພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ຊອກຫາການຕິດຕໍ່ກັນທົ່ວໄປໃນ 3 ເສັ້ນທີ່ມີຄວາມຍາວສູງສຸດ.

ວິທີການທີ່ໂງ່ຈ້າຂອງບັນຫາແມ່ນຂ້ອນຂ້າງຄ້າຍຄືກັບບັນຫາຕໍ່ໄປຂອງມະນຸດທີ່ຍາວນານທີ່ສຸດ. ພວກເຮົາໄດ້ປຶກສາຫາລືກ່ຽວກັບບັນຫາຕໍ່ມາ LongestCommon. ແຕ່ພວກເຮົາຍັງໄດ້ປຶກສາຫາລືວ່າວິທີການທີ່ໂງ່ຈ້າບໍ່ມີປະສິດທິພາບພຽງພໍທີ່ຈະແກ້ໄຂບັນຫາພາຍໃຕ້ເວລາທີ່ ກຳ ນົດ. ສະນັ້ນ, ເພື່ອແກ້ໄຂບັນຫາໂດຍບໍ່ໃຫ້ເກີນ ກຳ ນົດເວລາ. ພວກເຮົາຈະໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ສຳ ລັບການແກ້ໄຂ ຄຳ ຖາມ. ສະພາບການຈະຄ້າຍຄືກັບຂອງ LCS ສຳ ລັບ 2 ເຊືອກ. ໃນທີ່ນີ້ພວກເຮົາຈະມີ 3 ລັດເຊິ່ງຈະອ້າງເຖິງຕົວຊີ້ວັດໃນ 3 ເຊືອກທີ່ສອດຄ້ອງກັນ. ດັ່ງນັ້ນອາເລຂອງພວກເຮົາຈະເປັນແຖວ 3D, ບ່ອນທີ່ພວກເຮົາເກັບ 0 ຖ້າວ່າຕົວຊີ້ບອກໃດ ໜຶ່ງ ໃນ ຈຳ ນວນ 3 ຂອງມັນແມ່ນ 0. ຖ້າຕົວລະຄອນຢູ່ທັງສາມຕົວຊີ້ບອກແມ່ນຫຼັງຈາກນັ້ນພວກເຮົາເພີ່ມ 3 ຄຳ ຕອບ ສຳ ລັບໂຄງການຍ່ອຍ (LCS ຂອງ substrings ຈາກ ຄວາມຍາວ 1 ເຖິງ 0 ຫນ້ອຍກ່ວາແຕ່ລະຕົວຊີ້ວັດ). ຖ້າວ່າສາຍໃດ ໜຶ່ງ ຂອງສອງເສັ້ນບໍ່ມີລັກສະນະດຽວກັນພວກເຮົາເກັບສູງສຸດຂອງເຄື່ອງ ໝາຍ ຍ່ອຍບ່ອນທີ່ຫຼຸດລົງແຕ່ລະອັນດັບຂອງດັດຊະນີ ໜຶ່ງ ເທື່ອ.

ລະຫັດ

ລະຫັດ 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), ເພາະວ່າພວກເຮົາຕ້ອງໄດ້ຂ້າມ 3 ເຊືອກທີ່ມີຄວາມຍາວ N, M, ແລະ K. ຍ້ອນການໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ພວກເຮົາມີຄວາມສາມາດຫຼຸດຜ່ອນຄວາມສັບສົນທີ່ໃຊ້ເວລາກັບຫຼາຍຮູບແບບ.

ຄວາມສັບສົນໃນອະວະກາດ

O (N * M * K), ເນື່ອງຈາກວ່າພວກເຮົາຕ້ອງໄດ້ສ້າງຂອດ 3D DP ສຳ ລັບເກັບຮັກສາຜົນລັບ ສຳ ລັບໂຄງການຍ່ອຍນ້ອຍກວ່າແລະຈາກນັ້ນສົມທົບຜົນເພື່ອໃຫ້ໄດ້ ຄຳ ຕອບ ສຳ ລັບບັນຫາເບື້ອງຕົ້ນ. ດັ່ງນັ້ນການຊອກຫາ LCS (ຜົນກະທົບຕໍ່ທີ່ຍາວທີ່ສຸດ) ຂອງສາມສາຍມີຄວາມສັບສົນໃນອະວະກາດ.