Минимальные затраты на создание одинаковых двух строк

Опубликовано: 20 Января, 2022

Даны две строки X и Y и два значения costX и costY. Нам нужно найти минимальную стоимость, необходимую для того, чтобы данные две строки были идентичными. Мы можем удалять символы из обеих строк. Стоимость удаления символа из строки X - costX, а из Y - costY. Стоимость удаления всех символов из строки такая же.
Примеры :

 Ввод: X = "abcd", Y = "acdb", costX = 10, costY = 20.
Выход: 30
Чтобы сделать обе строки идентичными, мы должны удалить 
символ 'b' из обеих строк, следовательно, стоимость будет
быть = 10 + 20 = 30.

Ввод: X = "ef", Y = "gh", costX = 10, costY = 20.
Выход: 60
Чтобы сделать обе строки идентичными, мы должны удалить 2-2
символов из обеих строк, поэтому стоимость будет =
 10 + 10 + 20 + 20 = 60.

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Эта проблема является разновидностью самой длинной общей подпоследовательности (LCS). Идея проста: сначала мы находим длину самой длинной общей подпоследовательности строк X и Y. Теперь вычитание len_LCS из длин отдельных строк дает нам количество символов, которые нужно удалить, чтобы сделать их идентичными.

 // Стоимость совмещения двух строк равна СУММУ следующих двух
// 1) Стоимость удаления лишних символов (кроме LCS) 
// из X []
// 2) Стоимость удаления лишних символов (кроме LCS) 
// из Y []
Минимальные затраты на создание одинаковых строк = costX * (m - len_LCS) + 
                                         costY * (n - len_LCS).  

m ==> Длина строки X
m ==> Длина строки Y
len_LCS ==> Длина LCS X и Y.
costX ==> Стоимость удаления персонажа из X []
costY ==> Стоимость удаления символа из Y []

Обратите внимание, что стоимость удаления всех символов из строки
такой же.

Below is the implementation of above idea. 
 

C++

/* C++ code to find minimum cost to make two strings
   identical */
#include<bits/stdc++.h>
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
            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[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
/* 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++)
        {

РЕКОМЕНДУЕМЫЕ СТАТЬИ