Cerqueu si la cadena és k-palindroma o no | Estableix 2
Tenint en compte una cadena esbrineu si la cadena és k-palindrom o no. Una cadena K-Palindrom K es transforma en un palindrom en eliminar-ne la majoria de caràcters K.
Exemples:
Input : String - abcdecba k = 1 Output : Yes String can become palindrome by removing 1 character i.e. either d or e Input : String - abcdeca K = 2 Output : Yes Can become palindrome by removing 2 characters b and e (or b and d). Input : String - acdcb K = 1 Output : No String can not become palindrome by removing only one character.
Hem discutit una solució DP a previ post on vam veure que el problema és bàsicament una variació de Editar la distància problema. En aquesta publicació es discuteix una altra solució interessant de DP.
La idea és trobar la subseqüència palindròmica més llarga de la cadena donada. Si la diferència entre la subseqüència palindròmica més llarga i la cadena original és inferior a la igual a K, la cadena és k-palindrom, no és k-palindrom.
Per exemple, la subseqüència palindròmica més llarga de la cadena abcdeca és accdca (o aceca). S’han d’eliminar els caràcters que no contribueixen a la subseqüència palindròmica més llarga de la cadena per tal de fer la corda palindrom. Així doncs, en eliminar B i D (o E) de la cadena ABCDECA es transformarà en un palindroma.
Es pot trobar fàcilment la subseqüència palindròmica més llarga amb una cadena LCS . A continuació, es mostra la solució de dos passos per trobar una subseqüència palindròmica més llarga que utilitza LCS.
- Invertiu la seqüència donada i emmagatzemeu el revés en una altra matriu Say Rev [0..N-1]
- Els LC de la seqüència donada i Rev [] seran la seqüència palindròmica més llarga.
A continuació, es mostra la implementació de la idea anterior:
// C++ program to find if given string is K-Palindrome // or not #include using namespace std ; /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ int lcs ( string X string Y int m int n ) { int L [ m + 1 ][ n + 1 ]; /* 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 ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 || j == 0 ) L [ i ][ j ] = 0 ; else if ( X [ i - 1 ] == Y [ j - 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 and Y return L [ m ][ n ]; } // find if given string is K-Palindrome or not bool isKPal ( string str int k ) { int n = str . length (); // Find reverse of string string revStr = str ; reverse ( revStr . begin () revStr . end ()); // find longest palindromic subsequence of // given string int lps = lcs ( str revStr n n ); // If the difference between longest palindromic // subsequence and the original string is less // than equal to k then the string is k-palindrome return ( n - lps <= k ); } // Driver program int main () { string str = 'abcdeca' ; int k = 2 ; isKPal ( str k ) ? cout < < 'Yes' : cout < < 'No' ; return 0 ; }
Java // Java program to find if given // String is K-Palindrome or not import java.util.* ; import java.io.* ; class GFG { /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ static int lcs ( String X String Y int m int n ) { int L [][] = new int [ m + 1 ][ n + 1 ] ; /* 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 ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 || j == 0 ) { L [ i ][ j ] = 0 ; } else if ( X . charAt ( i - 1 ) == Y . charAt ( j - 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 and Y return L [ m ][ n ] ; } // find if given String is // K-Palindrome or not static boolean isKPal ( String str int k ) { int n = str . length (); // Find reverse of String StringBuilder revStr = new StringBuilder ( str ); revStr = revStr . reverse (); // find longest palindromic // subsequence of given String int lps = lcs ( str revStr . toString () n n ); // If the difference between longest // palindromic subsequence and the // original String is less than equal // to k then the String is k-palindrome return ( n - lps <= k ); } // Driver code public static void main ( String [] args ) { String str = 'abcdeca' ; int k = 2 ; if ( isKPal ( str k )) { System . out . println ( 'Yes' ); } else System . out . println ( 'No' ); } } // This code is contributed by Rajput-JI
Python3 # Python program to find # if given string is K-Palindrome # or not # Returns length of LCS # for X[0..m-1] Y[0..n-1] def lcs ( X Y m n ): L = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] # 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 not i or not j : L [ i ][ j ] = 0 elif X [ i - 1 ] == Y [ j - 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 and Y return L [ m ][ n ] # find if given string is # K-Palindrome or not def isKPal ( string k ): n = len ( string ) # Find reverse of string revStr = string [:: - 1 ] # find longest palindromic # subsequence of # given string lps = lcs ( string revStr n n ) # If the difference between # longest palindromic # subsequence and the original # string is less # than equal to k then # the string is k-palindrome return ( n - lps <= k ) # Driver program string = 'abcdeca' k = 2 print ( 'Yes' if isKPal ( string k ) else 'No' ) # This code is contributed # by Ansu Kumari.
C# // C# program to find if given // String is K-Palindrome or not using System ; class GFG { /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ static int lcs ( String X String Y int m int n ) { int [] L = new int [ m + 1 n + 1 ]; /* Following steps build L[m+1n+1] in bottom up fashion. Note that L[ij] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 || j == 0 ) { L [ i j ] = 0 ; } else if ( X [ i - 1 ] == Y [ j - 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[mn] contains length // of LCS for X and Y return L [ m n ]; } // find if given String is // K-Palindrome or not static bool isKPal ( String str int k ) { int n = str . Length ; // Find reverse of String str = reverse ( str ); // find longest palindromic // subsequence of given String int lps = lcs ( str str n n ); // If the difference between longest // palindromic subsequence and the // original String is less than equal // to k then the String is k-palindrome return ( n - lps <= k ); } static String reverse ( String input ) { char [] temparray = input . ToCharArray (); int left right = 0 ; right = temparray . Length - 1 ; for ( left = 0 ; left < right ; left ++ right -- ) { // Swap values of left and right char temp = temparray [ left ]; temparray [ left ] = temparray [ right ]; temparray [ right ] = temp ; } return String . Join ( '' temparray ); } // Driver code public static void Main ( String [] args ) { String str = 'abcdeca' ; int k = 2 ; if ( isKPal ( str k )) { Console . WriteLine ( 'Yes' ); } else Console . WriteLine ( 'No' ); } } // This code is contributed by PrinciRaj1992
JavaScript < script > // JavaScript program to find // if given string is K-Palindrome // or not // Returns length of LCS // for X[0..m-1] Y[0..n-1] function lcs ( X Y m n ){ let L = new Array ( m + 1 ); for ( let i = 0 ; i < m + 1 ; i ++ ){ L [ i ] = new Array ( n + 1 ). fill ( 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 ( let i = 0 ; i < m + 1 ; i ++ ) { for ( let j = 0 ; j < n + 1 ; j ++ ) { if ( ! i || ! j ) L [ i ][ j ] = 0 else if ( X [ i - 1 ] == Y [ j - 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 and Y return L [ m ][ n ] } // find if given string is // K-Palindrome or not function isKPal ( string k ){ let n = string . length // Find reverse of string let revStr = string . split ( '' ). reverse (). join ( '' ) // find longest palindromic // subsequence of // given string let lps = lcs ( string revStr n n ) // If the difference between // longest palindromic // subsequence and the original // string is less // than equal to k then // the string is k-palindrome return ( n - lps <= k ) } // Driver program let string = 'abcdeca' let k = 2 document . write ( isKPal ( string k ) ? 'Yes' : 'No' ) // This code is contributed by shinjanpatra < /script>
Producció
Yes
Complexitat temporal de la solució anterior és O (n 2 )).
Espai auxiliar utilitzat pel programa és O (n 2 )). Es pot reduir a més a O (n) mitjançant l'ús Solució optimitzada per l’espai de LCS .
Gràcies a El barranc que t’estrenyia per suggerir una solució anterior.
