Class StringInterleaving

java.lang.Object

topics.dynamic.stringinterleaving.StringInterleaving

public class StringInterleaving
extends Object

String Interleaving

Checks if string C is formed by an interleaving of strings A and B. Unlike the Greedy approach, Dynamic Programming guarantees the correct global optimum by exhaustively evaluating and memoizing all valid sub-paths.

The DP State Matrix

dp[i][j] represents whether the first i characters of A and the first j characters of B can form the first i + j characters of C.

• Time Complexity: O(N * M) - Where N and M are the lengths of strings A and B.
• Space Complexity: O(N * M) - To store the boolean evaluation matrix.

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
StringInterleaving()

Method Summary

Modifier and Type	Method	Description
boolean	isInterleaved(String a, String b, String c)	Solves the interleaving problem using a bottom-up 2D tabulation.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

StringInterleaving

public StringInterleaving()

Method Details

isInterleaved

public boolean isInterleaved(String a,
 String b,
 String c)

Solves the interleaving problem using a bottom-up 2D tabulation.

Parameters:

a - The first source string.

b - The second source string.

c - The target string to check.

Returns:

true if C is a valid interleaving of A and B.