Minimálne náklady na vytvorenie rovnakých dvoch strún
Vyskúšajte to na GfG Practice 
#practiceLinkDiv { display: none !important; }
Výstup
#practiceLinkDiv { display: none !important; } Dané dva reťazce X a Y a dve hodnoty costX a costY. Musíme nájsť minimálne náklady potrebné na to, aby boli dané dva reťazce identické. Môžeme odstrániť znaky z oboch reťazcov. Cena vymazania znaku z reťazca X je cenaX a z Y je cenaY. Náklady na odstránenie všetkých znakov z reťazca sú rovnaké.
Príklady:
Input : X = 'abcd' Y = 'acdb' costX = 10 costY = 20. Output: 30 For Making both strings identical we have to delete character 'b' from both the string hence cost will be = 10 + 20 = 30. Input : X = 'ef' Y = 'gh' costX = 10 costY = 20. Output: 60 For making both strings identical we have to delete 2-2 characters from both the strings hence cost will be = 10 + 10 + 20 + 20 = 60.Recommended Practice Minimálne náklady na vytvorenie rovnakých dvoch strún Skúste to!
Tento problém je variáciou najdlhšej spoločnej sekvencie (LCS) . Myšlienka je jednoduchá, najprv nájdeme dĺžku najdlhšej spoločnej podsekvencie reťazcov X a Y. Teraz odpočítaním len_LCS od dĺžky jednotlivých reťazcov dostaneme počet znakov, ktoré treba odstrániť, aby boli identické.
// Cost of making two strings identical is SUM of following two // 1) Cost of removing extra characters (other than LCS) // from X[] // 2) Cost of removing extra characters (other than LCS) // from Y[] Minimum Cost to make strings identical = costX * (m - len_LCS) + costY * (n - len_LCS). m ==> Length of string X m ==> Length of string Y len_LCS ==> Length of LCS Of X and Y. costX ==> Cost of removing a character from X[] costY ==> Cost of removing a character from Y[] Note that cost of removing all characters from a string is same.
Nižšie je uvedená implementácia vyššie uvedenej myšlienky.
C++ /* C++ code to find minimum cost to make two strings identical */ #include using namespace std ; /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ int lcs ( char * X char * 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[0..n-1] and Y[0..m-1] */ return L [ m ][ n ]; } // Returns cost of making X[] and Y[] identical. costX is // cost of removing a character from X[] and costY is cost // of removing a character from Y[]/ int findMinCost ( char X [] char Y [] int costX int costY ) { // Find LCS of X[] and Y[] int m = strlen ( X ) n = strlen ( Y ); int len_LCS = lcs ( X Y m n ); // Cost of making two strings identical is SUM of // following two // 1) Cost of removing extra characters // from first string // 2) Cost of removing extra characters from // second string return costX * ( m - len_LCS ) + costY * ( n - len_LCS ); } /* Driver program to test above function */ int main () { char X [] = 'ef' ; char Y [] = 'gh' ; cout < < 'Minimum Cost to make two strings ' < < ' identical is = ' < < findMinCost ( X Y 10 20 ); return 0 ; }
Java // Java code to find minimum cost to // make two strings identical 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[0..n-1] and Y[0..m-1] return L [ m ][ n ] ; } // Returns cost of making X[] and Y[] identical. // costX is cost of removing a character from X[] // and costY is cost of removing a character from Y[]/ static int findMinCost ( String X String Y int costX int costY ) { // Find LCS of X[] and Y[] int m = X . length (); int n = Y . length (); int len_LCS ; len_LCS = lcs ( X Y m n ); // Cost of making two strings identical // is SUM of following two // 1) Cost of removing extra characters // from first string // 2) Cost of removing extra characters // from second string return costX * ( m - len_LCS ) + costY * ( n - len_LCS ); } // Driver code public static void main ( String [] args ) { String X = 'ef' ; String Y = 'gh' ; System . out . println ( 'Minimum Cost to make two strings ' + ' identical is = ' + findMinCost ( X Y 10 20 )); } } // This code is contributed by vt_m
Python3 # Python code to find minimum cost # to make two strings identical # Returns length of LCS for # X[0..m-1] Y[0..n-1] def lcs ( X Y m n ): L = [[ 0 for i in range ( n + 1 )] for i 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 i == 0 or 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[0..n-1] and Y[0..m-1] return L [ m ][ n ] # Returns cost of making X[] # and Y[] identical. costX is # cost of removing a character # from X[] and costY is cost # of removing a character from Y[] def findMinCost ( X Y costX costY ): # Find LCS of X[] and Y[] m = len ( X ) n = len ( Y ) len_LCS = lcs ( X Y m n ) # Cost of making two strings # identical is SUM of following two # 1) Cost of removing extra # characters from first string # 2) Cost of removing extra # characters from second string return ( costX * ( m - len_LCS ) + costY * ( n - len_LCS )) # Driver Code X = 'ef' Y = 'gh' print ( 'Minimum Cost to make two strings ' end = '' ) print ( 'identical is = ' findMinCost ( X Y 10 20 )) # This code is contributed # by sahilshelangia
C# // C# code to find minimum cost to // make two strings identical 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+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 ] = 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] return L [ m n ]; } // Returns cost of making X[] and Y[] identical. // costX is cost of removing a character from X[] // and costY is cost of removing a character from Y[] static int findMinCost ( String X String Y int costX int costY ) { // Find LCS of X[] and Y[] int m = X . Length ; int n = Y . Length ; int len_LCS ; len_LCS = lcs ( X Y m n ); // Cost of making two strings identical // is SUM of following two // 1) Cost of removing extra characters // from first string // 2) Cost of removing extra characters // from second string return costX * ( m - len_LCS ) + costY * ( n - len_LCS ); } // Driver code public static void Main () { String X = 'ef' ; String Y = 'gh' ; Console . Write ( 'Minimum Cost to make two strings ' + ' identical is = ' + findMinCost ( X Y 10 20 )); } } // This code is contributed by nitin mittal.
PHP /* PHP code to find minimum cost to make two strings identical */ /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ 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 ]) $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] */ return $L [ $m ][ $n ]; } // Returns cost of making X[] and Y[] identical. costX is // cost of removing a character from X[] and costY is cost // of removing a character from Y[]/ function findMinCost ( & $X & $Y $costX $costY ) { // Find LCS of X[] and Y[] $m = strlen ( $X ); $n = strlen ( $Y ); $len_LCS = lcs ( $X $Y $m $n ); // Cost of making two strings identical is SUM of // following two // 1) Cost of removing extra characters // from first string // 2) Cost of removing extra characters from // second string return $costX * ( $m - $len_LCS ) + $costY * ( $n - $len_LCS ); } /* Driver program to test above function */ $X = 'ef' ; $Y = 'gh' ; echo 'Minimum Cost to make two strings ' . ' identical is = ' . findMinCost ( $X $Y 10 20 ); return 0 ; ?>
JavaScript < script > // Javascript code to find minimum cost to // make two strings identical // 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 ); } for ( let i = 0 ; i < m + 1 ; i ++ ) { for ( let j = 0 ; j < n + 1 ; j ++ ) { L [ i ][ j ] = 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 ; i ++ ) { for ( let 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[m][n] contains length of LCS // for X[0..n-1] and Y[0..m-1] return L [ m ][ n ]; } // Returns cost of making X[] and Y[] identical. // costX is cost of removing a character from X[] // and costY is cost of removing a character from Y[]/ function findMinCost ( X Y costX costY ) { // Find LCS of X[] and Y[] let m = X . length ; let n = Y . length ; let len_LCS ; len_LCS = lcs ( X Y m n ); // Cost of making two strings identical // is SUM of following two // 1) Cost of removing extra characters // from first string // 2) Cost of removing extra characters // from second string return costX * ( m - len_LCS ) + costY * ( n - len_LCS ); } // Driver code let X = 'ef' ; let Y = 'gh' ; document . write ( 'Minimum Cost to make two strings ' + ' identical is = ' + findMinCost ( X Y 10 20 )); // This code is contributed by avanitrachhadiya2155 < /script>
Výstup
Minimum Cost to make two strings identical is = 60
Časová zložitosť: O(m*n)
Pomocný priestor: O(m*n)
Tento článok je recenzovaný tímom geeksforgeeks.
