TCS Digital Capability Assessment Question 2

Write a program to find the number of ways in which we can transform a wrong word to a correct word by removing zero or more characters from the wrong word. Given: strings, i.e. S1 (for wrong word) and S2 (for correct word).

Instructions:

The system does not allow any kind of hard coded input value/values.

The written program code by the candidate will be verified against the inputs that are supplied from the system.

For more clarification, please read the following points carefully till the end.

Example 1:

Input :

Indiiian – String S1, i.e. wrong word

Indian – String S2, i.e. correct word

Output:

Explanation:

The three ways will be “ind..ian“, “indi.an” and “ind.i.an” , where ‘.’ is the place a character is removed

Example 2:

Input :

ggoog – String S1, i.e. wrong word

go – String S2, i.e. correct word

Output:

Explanation:

The four ways will be “g.o..“, “g..o.“, “.go..” and “.g.o.”
“.” is the place where characters are removed.

Program:

import java.util.Scanner;

public class TransformationWays {

	static int countTransformation(String str1, String str2) {
		int n = str1.length(), m = str2.length();

		// If b = "" i.e., an empty string. There
		// is only one way to transform (remove all
		// characters)
		if (m == 0) {
			return 1;
		}

		int dp[][] = new int[m][n];

		// Fill dp[][] in bottom up manner
		// Traverse all character of b[]
		for (int i = 0; i < m; i++) {

			// Traverse all charaters of a[] for b[i]
			for (int j = i; j < n; j++) {

				// Filling the first row of the dp
				// matrix.
				if (i == 0) {
					if (j == 0) {
						dp[i][j] = (str1.charAt(j) == str2.charAt(i)) ? 1 : 0;
					} else if (str1.charAt(j) == str2.charAt(i)) {
						dp[i][j] = dp[i][j - 1] + 1;
					} else {
						dp[i][j] = dp[i][j - 1];
					}
				}

				// Filling other rows.
				else if (str1.charAt(j) == str2.charAt(i)) {
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
				} else {
					dp[i][j] = dp[i][j - 1];
				}
			}
		}
		return dp[m - 1][n - 1];
	}
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String str1 = sc.next().trim();
		String str2 = sc.next().trim();
		

		System.out.println(countTransformation(str1, str2));
	}

}