អេសអេសអេស (ផលវិបាកបន្ទាប់វែងបំផុត) នៃខ្សែបី


កម្រិតលំបាក រឹង
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon លេខកូដ Expedia ក្រុមហ៊ុន google Uber Zoho
ការសរសេរកម្មវិធីឌីណាមិក ខ្សែអក្សរ

បញ្ហា“ អេសអិលអេសអេស (ផលប៉ះពាល់យូរបំផុត) នៃខ្សែរបី” ចែងថាអ្នកត្រូវបានផ្តល់ ៣ ខ្សែ។ ស្វែងយល់ពីបណ្តុំខ្សែវែងទាំងបីដែលវែងជាងគេបំផុត។ អេសអេសអេសគឺជាខ្សែដែលមានជាទូទៅក្នុងចំណោមខ្សែទាំង ៣ និងត្រូវបានបង្កើតឡើងដោយតួអក្សរដែលមានលំដាប់ដូចគ្នានៅក្នុងខ្សែទាំងអស់ដែលបានផ្តល់ឱ្យ។

ឧទាហរណ៍

អេសអេសអេស (ផលវិបាកបន្ទាប់វែងបំផុត) នៃខ្សែបី

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

វិធីសាស្រ្ត

បញ្ហាផ្តល់ឱ្យយើងនូវខ្សែបីដែលជាការបញ្ចូលហើយបានស្នើសុំឱ្យរកឱ្យឃើញនូវរឿងរ៉ាវដែលកើតឡើងជាយូរមកហើយទូទៅបំផុត។ ជាបន្តបន្ទាប់គឺជាខ្សែដែលនៅសល់នៅពេលយើងលុបតួអក្សរមួយចំនួនចេញពីខ្សែអក្សរដើម។ ដូច្ន្រះយើងត្រូវរកបនា្ទាប់រួមនៅក្នុងខ្សែចំនួនបីដ្រលមានប្រវែងអតិបរមា។

វិធីឆោតល្ងង់ចំពោះបញ្ហាគឺស្រដៀងគ្នាទៅនឹងបញ្ហាធម្មតាបន្ទាប់ដែលវែងបំផុត។ យើងបានពិភាក្សាអំពីបញ្ហាបន្ទាប់វែងបំផុត។ ប៉ុន្តែយើងក៏បានពិភាក្សាផងដែរថាវិធីឆោតល្ងង់មិនមានប្រសិទ្ធភាពគ្រប់គ្រាន់ក្នុងការដោះស្រាយបញ្ហាក្រោមពេលវេលាកំណត់ទេ។ ដូច្នេះដើម្បីដោះស្រាយបញ្ហាដោយមិនឱ្យលើសពីពេលវេលាកំណត់។ យើងនឹងប្រើ ការសរសេរកម្មវិធីថាមវន្ត សម្រាប់ការដោះស្រាយសំណួរ។ លក្ខខណ្ឌនឹងស្រដៀងនឹងអេសអេសអេសសម្រាប់ 2 ខ្សែ។ នៅទីនេះយើងនឹងមានរដ្ឋចំនួន ៣ ដែលនឹងយោងទៅលើសូចនាករនៅក្នុងខ្សែ ៣ ដែលត្រូវគ្នា។ ដូច្នេះអារេឌីអេចរបស់យើងនឹងជាអារេត្រីមាត្រដែលយើងរក្សាទុក ០ ប្រសិនបើសូចនាករណាមួយក្នុងចំណោម ៣ ក្នុងចំណោមនោះគឺ ០ ។ ប្រសិនបើតួអក្សរនៅចង្អុលបង្ហាញទាំង ៣ គឺបន្ទាប់មកយើងបន្ថែមលេខ ១ ទៅចម្លើយសំរាប់គំរោងរង (អិម។ ស។ នៃផ្នែករងពី ប្រវែង ០ ដល់ ១ តិចជាងសូចនាករនីមួយៗ) ។ ប្រសិនបើខ្សែណាមួយក្នុងចំណោមខ្សែទាំងពីរមិនមានតួអក្សរដូចគ្នានោះយើងរក្សាទុកអតិបរិមានៃវត្ថុរងដែលការថយចុះនៃសន្ទស្សន៍នីមួយៗម្តងមួយៗ។

លេខកូដ

លេខកូដ 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

កូដចាវ៉ាដើម្បីរកខ្សែអេសអេសអេសចំនួន ៣ ខ្សែ

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), ពីព្រោះយើងត្រូវបង្កើតអាដាប់ធ័រឌី។ ឌី។ អ។ ឌី។ ឌី។ សម្រាប់រក្សាទុកលទ្ធផលសំរាប់អនុរងតូចៗហើយបន្ទាប់មកផ្សំលទ្ធផលដើម្បីទទួលបានចម្លើយសម្រាប់បញ្ហាដំបូង។ ដូច្នេះការស្វែងរកអេសអេសអេសអេសអេស (ផលវិបាកយូរអង្វែងយូរបំផុត) នៃខ្សែបីមានភាពស្មុគស្មាញនៃពហុកោណ។