Implement Check if it is possible to transform one string to another.

[AnuradhaPagare]

Statement Given two strings s1 and s2 (all letters in uppercase). Check if it is possible to convert s1 to s2 by performing following operations.

1. Make some lowercase letters uppercase.
2. Delete all the lowercase letters.
   Input: s1 = daBcd s2 = ABC Output: yes Input: s1 = argaju s2 = RAJ Output: yes

public class StringTransformation {

// Function to check if s1 can be transformed to s2
public static boolean canTransform(String s1, String s2) {
    int m = s1.length();
    int n = s2.length();

    // If s2 is longer than s1, it's impossible to transform
    if (n > m) return false;

    // Create a 2D DP array
    boolean[][] dp = new boolean[m + 1][n + 1];

    // Initialize dp[0][0] = true
    dp[0][0] = true;

    // Fill the DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            // Case 1: Ignore the current character in s1 if it is lowercase
            if (Character.isLowerCase(s1.charAt(i - 1))) {
                dp[i][j] = dp[i - 1][j];
            }

            // Case 2: Match the character (if possible)
            if (j > 0 && Character.toUpperCase(s1.charAt(i - 1)) == s2.charAt(j - 1)) {
                dp[i][j] |= dp[i - 1][j - 1];
            }
        }
    }

    // The answer is in dp[m][n]
    return dp[m][n];
}

public static void main(String[] args) {
    // Test cases
    String s1 = "daBcd";
    String s2 = "ABC";
    System.out.println(canTransform(s1, s2) ? "yes" : "no");  // Output: yes

    s1 = "argaju";
    s2 = "RAJ";
    System.out.println(canTransform(s1, s2) ? "yes" : "no");  // Output: yes

    s1 = "abcde";
    s2 = "ABCDE";
    System.out.println(canTransform(s1, s2) ? "yes" : "no");  // Output: yes

    s1 = "abcdef";
    s2 = "AXYZ";
    System.out.println(canTransform(s1, s2) ? "yes" : "no");  // Output: no
}

}

[AnuradhaPagare]

Control Abstraction for the same code.

Transform(s1, s2): m ← length of s1 n ← length of s2 Create a DP table dp[m+1][n+1]

// Base Case: Both strings are empty
dp[0][0] ← true

// Fill the DP table
for i from 1 to m:
    for j from 0 to n:
        // Case 1: Ignore the current character in s1 if it is lowercase
        if isLowerCase(s1[i]):
            dp[i][j] ← dp[i-1][j]

        // Case 2: Match the character if possible
        if j > 0 and toUpperCase(s1[i]) == s2[j]:
            dp[i][j] ← dp[i][j] OR dp[i-1][j-1]

// Final decision
return dp[m][n]