Poiščite, če je niz k-palindrom ali ne | Set 2
Glede na niz ugotovite, ali je niz k-palindrom ali ne. K-palindromski niz se spremeni v palindrom, ko odstrani največ k likov iz njega.
Primeri:
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.
Smo razpravljali o rešitvi DP v Prejšnji Objava, kjer smo videli, da je težava v bistvu različica Urejanje razdalje problem. V tej objavi je obravnavana še ena zanimiva rešitev DP.
Ideja je najti najdaljšo palindromsko sled danega niza. Če je razlika med najdaljšim palindromskim naknazom in prvotnim nizom manjša od K, potem je niz k-palindrom drugače, to ni k-palindrom.
Na primer najdaljša palindromska naknadna sled niza ABCDECA je ACCDCA (ali aceca). Like, ki ne prispevajo k najdaljši palindromski naknad niza, je treba odstraniti, da se vrvi palindrom naredi. Tako se bo ob odstranitvi B in D (ali E) iz niza ABCDECA spremenil v palindrom.
Najdaljši palindromski naknad niza je mogoče zlahka najti s pomočjo LCS . Sledi rešitev dveh korakov za iskanje najdaljše palindromske naknade, ki uporablja LCS.
- Obrnite dano zaporedje in shranite obratno v drugi matriki, recimo rev [0..N-1]
- LCS danega zaporedja in Rev [] bodo najdaljše palindromsko zaporedje.
Spodaj je izvedba zgornje ideje -
// 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>
Izhod
Yes
Časovna zapletenost zgornje raztopine je o (n 2 ).
Pomožni prostor Uporablja program O (n 2 ). Z uporabo je mogoče nadalje zmanjšati na O (n) Raztopina LCS, optimizirana za vesolje .
Hvala Računa si zožila za predlaganje zgornje rešitve.
