包含最长元音子序列的最长元音-yiteyi-C++库

给两条线十、和 Y 长度 M 和 N 分别地问题是找到最长公共子串的长度十、和 Y 包含所有元音字符。

null

例如：

Input : X = "aieef"         Y = "klaief"Output : aieInput : X = "geeksforgeeks"         Y = "feroeeks"Output : eoee

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

资料来源： Paytm面试经验（后端开发人员）。 天真的方法： 生成两个给定序列的所有子序列，并找到包含所有元音字符的最长匹配子序列。这个解决方案的时间复杂度是指数的。

有效方法（动态规划）： 这种方法是对最长公共子序列| DP-4 问题

这篇文章的不同之处在于，常见的子序列字符都必须是元音。

C++

                         // C++ implementation to find the length of longest common                       
                         // subsequence which contains all vowel characters                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // function to check whether 'ch'                       
                         // is a vowel or not                       
                         bool                                     isVowel(                                     char                                     ch)                       
                         {                       
                                                 if                                     (ch ==                                     'a'                                     || ch ==                                     'e'                                     || ch ==                                     'i'                       
                                                 || ch ==                                     'o'                                     || ch ==                                     'u'                                     )                       
                                                 return                                     true                                     ;                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // function to find the length of longest common subsequence                       
                         // which contains all vowel characters                       
                         int                                     lcs(                                     char                                     * X,                                     char                                     * Y,                                     int                                     m,                                     int                                     n)                       
                         {                       
                                                 int                                     L[m + 1][n + 1];                       
                                                 int                                     i, j;                       
           
                                                 // Following steps build L[m+1][n+1] in bottom up fashion. Note                       
                                                 // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]                       
                                                 for                                     (i = 0; i <= m; i++) {                       
                                                 for                                     (j = 0; j <= n; j++) {                       
                                                 if                                     (i == 0 || j == 0)                       
                                                 L[i][j] = 0;                       
           
                                                 else                                     if                                     ((X[i - 1] == Y[j - 1]) && isVowel(X[i - 1]))                       
                                                 L[i][j] = L[i - 1][j - 1] + 1;                       
           
                                                 else                       
                                                 L[i][j] = max(L[i - 1][j], L[i][j - 1]);                       
                                                 }                       
                                                 }                       
           
                                                 // L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]                       
                                                 // which contains all vowel characters                       
                                                 return                                     L[m][n];                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 char                                     X[] =                                     "aieef"                                     ;                       
                                                 char                                     Y[] =                                     "klaief"                                     ;                       
           
                                                 int                                     m =                                     strlen                                     (X);                       
                                                 int                                     n =                                     strlen                                     (Y);                       
           
                                                 cout <<                                     "Length of LCS = "                       
                                                 << lcs(X, Y, m, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to find the                       
                         // length of longest common subsequence                       
                         // which contains all vowel characters                       
                         class                                     GFG                       
                         {                       
           
                         // function to check whether 'ch'                       
                         // is a vowel or not                       
                         static                                     boolean                                     isVowel(                                     char                                     ch)                       
                         {                       
                                                 if                                     (ch ==                                     'a'                                     || ch ==                                     'e'                                     ||                       
                                                 ch ==                                     'i'                                     || ch ==                                     'o'                                     ||                       
                                                 ch ==                                     'u'                                     )                       
                                                 return                                     true                                     ;                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // function to find the length of                       
                         // longest common subsequence which                       
                         // contains all vowel characters                       
                         static                                     int                                     lcs(String X, String Y,                       
                                                 int                                     m,                                     int                                     n)                       
                         {                       
                                                 int                                     L[][] =                                     new                                     int                                     [m +                                     1                                     ][n +                                     1                                     ];                       
                                                 int                                     i, j;                       
           
                                                 // Following steps build L[m+1][n+1]                       
                                                 // in bottom up fashion. Note that                       
                                                 // L[i][j] contains length of LCS of                       
                                                 // X[0..i-1] and Y[0..j-1]                       
                                                 for                                     (i =                                     0                                     ; i <= m; i++)                       
                                                 {                       
                                                 for                                     (j =                                     0                                     ; j <= n; j++)                       
                                                 {                       
                                                 if                                     (i ==                                     0                                     || j ==                                     0                                     )                       
                                                 L[i][j] =                                     0                                     ;                       
           
                                                 else                                     if                                     ((X.charAt(i -                                     1                                     ) == Y.charAt(j -                                     1                                     )) &&                       
                                                 isVowel(X.charAt(i -                                     1                                     )))                       
                                                 L[i][j] = L[i -                                     1                                     ][j -                                     1                                     ] +                                     1                                     ;                       
           
                                                 else                       
                                                 L[i][j] = Math.max(L[i -                                     1                                     ][j],                       
                                                 L[i][j -                                     1                                     ]);                       
                                                 }                       
                                                 }                       
           
                                                 // L[m][n] contains length of LCS                       
                                                 // for X[0..n-1] and Y[0..m-1]                       
                                                 // which contains all vowel characters                       
                                                 return                                     L[m][n];                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 String X =                                     "aieef"                                     ;                       
                                                 String Y =                                     "klaief"                                     ;                       
           
                                                 int                                     m = X.length();                       
                                                 int                                     n = Y.length();                       
           
                                                 System.out.println(                                     "Length of LCS = "                                     +                       
                                                 lcs(X, Y, m, n));                       
                         }                       
                         }                       
           
                         // This code is contributed by Bilal                       

Python3

                         # Python3 implementation to find the                       
                         # length of longest common subsequence                       
                         # which contains all vowel characters                       
           
                         # function to check whether 'ch'                       
                         # is a vowel or not                       
                         def                                     isVowel(ch):                       
                                                 if                                     (ch                                     =                                     =                                     'a'                                     or                                     ch                                     =                                     =                                     'e'                                     or                       
                                                 ch                                     =                                     =                                     'i'                                     or                                     ch                                     =                                     =                                     'o'                                     or                       
                                                 ch                                     =                                     =                                     'u'                                     ):                       
                                                 return                                     True                       
                                                 return                                     False                       
           
                         # function to find the length of longest                       
                         # common subsequence which contains all                       
                         # vowel characters                       
                         def                                     lcs(X, Y, m, n):                       
           
                                                 L                                     =                                     [[                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                                 for                                     j                                     in                                     range                                     (m                                     +                                     1                                     )]                       
                                                 i, j                                     =                                     0                                     ,                                     0                       
                                   
                                                 # Following steps build L[m+1][n+1] in                       
                                                 # bottom up fashion. Note that L[i][j]                       
                                                 # contains length of LCS of X[0..i-1]                       
                                                 # and Y[0..j-1]                       
                                                 for                                     i                                     in                                     range                                     (m                                     +                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (n                                     +                                     1                                     ):                       
                                                 if                                     (i                                     =                                     =                                     0                                     or                                     j                                     =                                     =                                     0                                     ):                       
                                                 L[i][j]                                     =                                     0                       
                                                 elif                                     ((X[i                                     -                                     1                                     ]                                     =                                     =                                     Y[j                                     -                                     1                                     ])                                     and                       
                                                 isVowel(X[i                                     -                                     1                                     ])):                       
                                                 L[i][j]                                     =                                     L[i                                     -                                     1                                     ][j                                     -                                     1                                     ]                                     +                                     1                       
                                                 else                                     :                       
                                                 L[i][j]                                     =                                     max                                     (L[i                                     -                                     1                                     ][j],                       
                                                 L[i][j                                     -                                     1                                     ])                       
                                   
                                                 # L[m][n] contains length of LCS for                       
                                                 # X[0..n-1] and Y[0..m-1] which                       
                                                 # contains all vowel characters                       
                                                 return                                     L[m][n]                       
           
                         # Driver Code                       
                         X                                     =                                     "aieef"                       
                         Y                                     =                                     "klaief"                       
           
                         m                                     =                                     len                                     (X)                       
                         n                                     =                                     len                                     (Y)                       
           
                         print                                     (                                     "Length of LCS ="                                     , lcs(X, Y, m, n))                       
           
                         # This code is contributed by Mohit Kumar                       

C#

                         // C# implementation to find the                       
                         // length of longest common subsequence                       
                         // which contains all vowel characters                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // function to check whether                       
                         // 'ch' is a vowel or not                       
                         static                                     int                                     isVowel(                                     char                                     ch)                       
                         {                       
                                                 if                                     (ch ==                                     'a'                                     || ch ==                                     'e'                                     ||                       
                                                 ch ==                                     'i'                                     || ch ==                                     'o'                                     ||                       
                                                 ch ==                                     'u'                                     )                       
                                                 return                                     1;                       
                                                 return                                     0;                       
                         }                       
           
                         // find max value                       
                         static                                     int                                     max(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 return                                     (a > b) ? a : b;                       
                         }                       
           
                         // function to find the length of                       
                         // longest common subsequence which                       
                         // contains all vowel characters                       
                         static                                     int                                     lcs(String X, String Y,                       
                                                 int                                     m,                                     int                                     n)                       
                         {                       
                                                 int                                     [,]L =                                     new                                     int                                     [m + 1, n + 1];                       
                                                 int                                     i, j;                       
           
                                                 // Following steps build L[m+1,n+1]                       
                                                 // in bottom up fashion. Note that                       
                                                 // L[i,j] contains length of LCS of                       
                                                 // X[0..i-1] and Y[0..j-1]                       
                                                 for                                     (i = 0; i <= m; i++)                       
                                                 {                       
                                                 for                                     (j = 0; j <= n; j++)                       
                                                 {                       
                                                 if                                     (i == 0 || j == 0)                       
                                                 L[i, j] = 0;                       
           
                                                 else                                     if                                     ((X[i - 1] == Y[j - 1]) &&                       
                                                 isVowel(X[i - 1]) == 1)                       
                                                 L[i, j] = L[i - 1, j - 1] + 1;                       
                                   
                                                 else                       
                                                 L[i, j] = max(L[i - 1, j],                       
                                                 L[i, j - 1]);                       
                                                 }                       
                                                 }                       
           
                                                 // L[m,n] contains length of LCS                       
                                                 // for X[0..n-1] and Y[0..m-1]                       
                                                 // which contains all vowel characters                       
                                                 return                                     L[m, n];                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main(String []args)                       
                         {                       
                                                 String X =                                     "aieef"                                     ;                       
                                                 String Y =                                     "klaief"                                     ;                       
           
                                                 int                                     m = X.Length;                       
                                                 int                                     n = Y.Length;                       
           
                                                 Console.WriteLine(                                     "Length of LCS = "                                     +                       
                                                 lcs(X, Y, m, n));                       
                         }                       
                         }                       
           
                         // This code is contributed by Arnab Kundu                       

PHP

                         <?php                       
                         // PHP implementation to find the length of                       
                         // longest common subsequence which contains                       
                         // all vowel characters                       
           
                         // function to check whether 'ch'                       
                         // is a vowel or not                       
                         function                                     isVowel(                                     $ch                                     )                       
                         {                       
                                                 if                                     (                                     $ch                                     ==                                     'a'                                     ||                                     $ch                                     ==                                     'e'                                     ||                       
                                                 $ch                                     ==                                     'i'                                     ||                                     $ch                                     ==                                     'o'                                     ||                                     $ch                                     ==                                     'u'                                     )                       
                                                 return                                     true;                       
                                                 return                                     false;                       
                         }                       
           
                         // function to find the length of longest common                       
                         // subsequence which contains all vowel characters                       
                         function                                     lcs(                                     $X                                     ,                                     $Y                                     ,                                     $m                                     ,                                     $n                                     )                       
                         {                       
                                                 $L                                     =                                     array_fill                                     (0,                                     $m                                     + 1,                                     array_fill                                     (0,                                     $n                                     + 1, NULL));                       
           
                                                 // Following steps build L[m+1][n+1] in bottom                       
                                                 // up fashion. Note that L[i][j] contains length                       
                                                 // of LCS of X[0..i-1] and Y[0..j-1]                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <=                                     $m                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <=                                     $n                                     ;                                     $j                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $i                                     == 0 ||                                     $j                                     == 0)                       
                                                 $L                                     [                                     $i                                     ][                                     $j                                     ] = 0;                       
           
                                                 else                                     if                                     ((                                     $X                                     [                                     $i                                     - 1] ==                                     $Y                                     [                                     $j                                     - 1]) &&                       
                                                 isVowel(                                     $X                                     [                                     $i                                     - 1]))                       
                                                 $L                                     [                                     $i                                     ][                                     $j                                     ] =                                     $L                                     [                                     $i                                     - 1][                                     $j                                     - 1] + 1;                       
           
                                                 else                       
                                                 $L                                     [                                     $i                                     ][                                     $j                                     ] = max(                                     $L                                     [                                     $i                                     - 1][                                     $j                                     ],                       
                                                 $L                                     [                                     $i                                     ][                                     $j                                     - 1]);                       
                                                 }                       
                                                 }                       
           
                                                 // L[m][n] contains length of LCS for X[0..n-1]                       
                                                 // and Y[0..m-1] which contains all vowel characters                       
                                                 return                                     $L                                     [                                     $m                                     ][                                     $n                                     ];                       
                         }                       
           
                         // Driver Code                       
                         $X                                     =                                     "aieef"                                     ;                       
                         $Y                                     =                                     "klaief"                                     ;                       
           
                         $m                                     =                                     strlen                                     (                                     $X                                     );                       
                         $n                                     =                                     strlen                                     (                                     $Y                                     );                       
           
                         echo                                     "Length of LCS = "                                     . lcs(                                     $X                                     ,                                     $Y                                     ,                                     $m                                     ,                                     $n                                     );                       
           
                         // This code is contributed by ita_c                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript implementation to find the                       
                         // length of longest common subsequence                       
                         // which contains all vowel characters                       
           
                         // Function to check whether 'ch'                       
                         // is a vowel or not                       
                         function                                     isVowel(ch)                       
                         {                       
                                                 if                                     (ch ==                                     'a'                                     || ch ==                                     'e'                                     ||                       
                                                 ch ==                                     'i'                                     || ch ==                                     'o'                                     ||                       
                                                 ch ==                                     'u'                                     )                       
                                                 return                                     true                                     ;                       
                                   
                                                 return                                     false                                     ;                       
                         }                       
           
                         // Function to find the length of                       
                         // longest common subsequence which                       
                         // contains all vowel characters                       
                         function                                     lcs(X, Y, m, n)                       
                         {                       
                                                 let L =                                     new                                     Array(m + 1);                       
                                                 let i, j;                       
                                   
                                                 // Following steps build L[m+1][n+1]                       
                                                 // in bottom up fashion. Note that                       
                                                 // L[i][j] contains length of LCS of                       
                                                 // X[0..i-1] and Y[0..j-1]                       
                                                 for                                     (i = 0; i <= m; i++)                       
                                                 {                       
                                                 L[i] =                                     new                                     Array(n + 1);                       
                                                 for                                     (j = 0; j <= n; j++)                       
                                                 {                       
                                                 if                                     (i == 0 || j == 0)                       
                                                 L[i][j] = 0;                       
                                   
                                                 else                                     if                                     ((X[i - 1] == Y[j - 1]) &&                       
                                                 isVowel(X[i - 1]))                       
                                                 L[i][j] = L[i - 1][j - 1] + 1;                       
                                   
                                                 else                       
                                                 L[i][j] = Math.max(L[i - 1][j],                       
                                                 L[i][j - 1]);                       
                                                 }                       
                                                 }                       
                                   
                                                 // L[m][n] contains length of LCS                       
                                                 // for X[0..n-1] and Y[0..m-1]                       
                                                 // which contains all vowel characters                       
                                                 return                                     L[m][n];                       
                         }                       
           
                         // Driver Code                       
                         let X =                                     "aieef"                                     ;                       
                         let Y =                                     "klaief"                                     ;                       
                         let m = X.length;                       
                         let n = Y.length;                       
           
                         document.write(                                     "Length of LCS = "                                     + lcs(X, Y, m, n));                       
           
                         // This code is contributed by avanitrachhadiya2155                       
           
                         </script>                       

输出：

Length of LCS = 3

时间复杂性： O（m*n）。 辅助空间： O（m*n）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章