//{ 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]; } }