Class StringInterleaving

java.lang.Object

topics.divideconquer.stringinterleaving.StringInterleaving

public class StringInterleaving
extends Object

String Interleaving

Checks if string C is formed by an interleaving of strings A and B by recursively breaking the problem down into smaller sub-problems (advancing character pointers).

Pedagogical Value

This pure recursive approach acts as the mathematical bridge between Greedy and Dynamic Programming:

• Unlike Greedy, it does not get trapped by ambiguity. If characters from A and B both match C, it branches and explores both possibilities.
• Unlike Dynamic Programming, it does not memorize past results. This leads to overlapping sub-problems being recalculated multiple times.

• Time Complexity: O(2^(N+M)) in the worst case (Exponential due to branching).
• Space Complexity: O(N+M) - Bounded by the maximum depth of the call stack.

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
StringInterleaving()

Method Summary

Modifier and Type	Method	Description
boolean	isInterleaved(String a, String b, String c)	Public wrapper method to initialize the recursion safely.

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)

Public wrapper method to initialize the recursion safely.

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.