Find, om streng er k-palindrome eller ej | Sæt 2
Givet en streng Find ud af, om strengen er K-Palindrome eller ej. En K-Palindrome-streng omdannes til en palindrom ved at fjerne de fleste K-tegn fra den.
Eksempler:
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.
Vi har drøftet en DP -løsning i tidligere post, hvor vi så, at problemet dybest set er en variation af Rediger afstand problem. I dette indlæg diskuteres en anden interessant DP -løsning.
Ideen er at finde den længste palindromiske efterfølgende af den givne streng. Hvis forskellen mellem den længste palindromiske efterfølgende og den originale streng er mindre end lig med K, er strengen k-palindrom ellers er den ikke K-Palindrome.
For eksempel længst palindromisk efterfølgende streng Abcdeca er Accdca (eller ACECA). De tegn, der ikke bidrager til længst palindromisk efterfølgende af strengen, skal fjernes for at gøre strengen palindrome. Så ved fjernelse af B og D (eller E) fra Abcdeca -streng omdannes til en palindrome.
Den længste palindromiske efterfølgende af en streng kan let findes ved hjælp af LCS . Følgende er den to -trins løsning til at finde den længste palindromiske efterfølgende, der bruger LCS.
- Vend den givne sekvens, og gem det modsatte i en anden matrix Say Rev [0..N-1]
- LC'er af den givne sekvens og Rev [] vil være den længste palindromiske sekvens.
Nedenfor er implementeringen af ovenstående idé -
// 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>
Produktion
Yes
Tidskompleksitet af ovenstående løsning er o (n 2 ).
Hjælpeplads Brugt af programmet er O (n 2 ). Det kan yderligere reduceres til O (n) ved at bruge Rumoptimeret løsning af LC'er .
Tak til Ravine du indsnævret For at foreslå ovenstående løsning.
