//{ 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]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter