Q41 Minimum Cost To Make Two Strings Identical | Practice | GeeksforGeeks

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;
class GfG
{
    public static void main(String args[])
        {
            Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            while(t-->0)
                {
                    String X = sc.next();
                    String Y = sc.next();
                    int costX = sc.nextInt();
                    int costY = sc.nextInt();
                    
                   
                    Solution ob = new Solution();
                    System.out.println(ob.findMinCost(X,Y,costX,costY));
                }
        }
}    
// } Driver Code Ends


//User function Template for Java

class Solution
{
	public int findMinCost(String s1, String s2, int costX, int costY)
	{
		//similiar to Leetcode 712, minimum cost(MC)
 
        //every cell will store MC for ith string to be equal to jth string
 
        int m = s1.length() , n = s2.length();
        int[][] dp = new int[m+1][n+1];     //+1 for empty string
 
        //last row and last col will be 0
        
        for(int i = m; i>=0 ;i--){
 
            for(int j = n ; j>=0 ; j--){
                
                //last cell
                if(i == m && j == n)
                dp[i][j] = 0;
                
                //last col , we will have to delete all chars to match "-"
                else if(j == n)
                dp[i][j] = dp[i+1][j] + costX;
 
                //last row , we will have to delete all chars to match "-"
                else if(i == m)
                dp[i][j] = dp[i][j+1] + costY;
 
                //ROD - rest of the dp
                else{
                    //if chars are equal check diagonally forward
                    if(s1.charAt(i) == s2.charAt(j))
                    dp[i][j] = dp[i+1][j+1];
                    
                    /*removing first char of str1 and checking MC with ros str2
                    and vice versa ...and also removing both and checking
                    diagonally....and taking minimum of all and adding the
                    the cost value of character removed
                    */
                    else{
                        int MC1 = dp[i+1][j] + costX;
                        int MC2 = dp[i][j+1] + costY;
                        int MC3 = dp[i+1][j+1] + costX + costY;
                        dp[i][j] = Math.min(MC1 , Math.min(MC2,MC3));
                    }
                }
            }
        }
 
        return dp[0][0];
	}
}