Check if a String is a Valid Shuffle of Two Distinct Strings

Java Program to Check if a String is a Valid Shuffle of Two Distinct Strings

In the realm of string manipulation, one interesting challenge is to determine whether a given string is a valid shuffle of two distinct strings. This problem involves checking if the characters of two input strings can be interleaved to form a third string while preserving the order of characters from the original strings.

Problem Definition

Given three strings:

• s1: The first input string.
• s2: The second input string.
• s3: The string we want to check if it is a valid shuffle of s1 and s2.

A valid shuffle means that:

1. The length of s3 should be equal to the sum of the lengths of s1 and s2.
2. The characters in s3 must consist of all characters from s1 and s2, and their order in s3 should maintain the relative order of characters from s1 and s2.

Example

Input: s1 = "abc", s2 = "def", s3 = "adbcef"

Output: true (since s3 can be formed by interleaving s1 and s2)

Input: s1 = "abc", s2 = "def", s3 = "abdecf"

Output: false (since the order of characters from s1 and s2 is not preserved)

Implementation

To solve this problem, we can use dynamic programming (DP). We will create a 2D boolean array to store whether a substring of s3 can be formed by interleaving substrings of s1 and s2. Here’s the step-by-step approach:

1. Check the length of s3 against the combined lengths of s1 and s2.
2. Create a DP table where dp[i][j] indicates whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3.
3. Fill in the DP table based on the characters in s1, s2, and s3.
4. Return the value at dp[s1.length()][s2.length()].

Here’s the Java code that implements the above logic:

public class StringShuffleChecker {
    
    public static boolean isValidShuffle(String s1, String s2, String s3) {
        // Check lengths
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        // Create a DP table
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];

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

        // Fill the first row
        for (int j = 1; j <= s2.length(); j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        // Fill the first column
        for (int i = 1; i <= s1.length(); i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }

        // Fill the rest of the DP table
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                           (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        return dp[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        String s1 = "abc";
        String s2 = "def";
        String s3 = "adbcef";

        boolean result = isValidShuffle(s1, s2, s3);
        System.out.println("Is \"" + s3 + "\" a valid shuffle of \"" + s1 + "\" and \"" + s2 + "\"? " + result);
    }
}

Explanation of the Code

The method isValidShuffle takes three strings as input and initializes a 2D boolean array dp to keep track of valid shuffles.

It fills the first row and the first column based on whether the characters of s2 and s1 match with s3.

The nested loops then fill in the rest of the DP table based on whether characters from either s1 or s2 can contribute to forming the current character in s3.

Finally, it returns the value of dp[s1.length()][s2.length()], which indicates if s3 can be formed from s1 and s2.

Conclusion

In this blog post, we explored a Java implementation for checking if a string is a valid shuffle of two distinct strings. The approach leverages dynamic programming to efficiently determine if the characters from the two strings can interleave to form the third string while preserving order. This technique can be useful in various applications such as text processing, data validation, and more.

Feel free to experiment with the code and explore different combinations of strings to see how the algorithm performs! Happy coding!