Q50 Distinct Transformation LeetCode Playground ( tabulization approach)
Fri Mar 31 2023 11:41:41 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;
public class main {
public static int solution(String s1 , String s2 ){//s2 is target
//tabulization approach -> every cell denotes total no. of way of making
//ith string from jth string if only deletion is allowed
//make dp with target on rows and source on coloumns
int n = s1.length() , m = s2.length();
int dp[][] = new int[m+1][n+1];
for(int i = m ; i>=0 ; i--){
for(int j = n ; j>=0 ; j--){
//if last cell ->1
if(i == m & j==n)
dp[i][j] =1;
//if last row ->1
else if(i == m)
dp[i][j] = 1;
//if last col -> 0
else if(j == n)
dp[i][j] = 0;
//rest of the dp
else{
char ch1 = s2.charAt(i) , ch2 = s1.charAt(j);
//if chars are not equal we remove character from source
if(ch1 != ch2)
dp[i][j] = dp[i][j+1];
//if chars are equal we remove character from source & we match
//both characters
else
dp[i][j] = dp[i+1][j+1] + dp[i][j+1];
}
}
}
for(int i = 0 ; i < dp.length ; i++){
for(int j = 0 ; j < dp[0].length ; j++)
System.out.print(dp[i][j] + " ");
System.out.println();
}
return dp[0][0];
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
String s1 = scn.next();
String s2 = scn.next();
int[][] dp = new int[s1.length()][s2.length()];
System.out.println(solution(s1, s2 ));
}
}
content_copyCOPY
https://leetcode.com/playground/2nCsfjag
Comments