Class StringInterleavingGenerator

java.lang.Object
topics.backtracking.stringinterleaving.StringInterleavingGenerator
public class StringInterleavingGenerator extends Object

String Interleaving Generator

Instead of verifying a single target string, this algorithm exhaustively generates EVERY possible valid interleaving of two strings, maintaining the relative order of their characters.

The Backtracking Paradigm

Notice the core pattern inside the recursive method:

  1. CHOOSE: We append a character to our current path.
  2. EXPLORE: We recurse deeper into the tree.
  3. UN-CHOOSE: We delete the character to backtrack and try a parallel branch.

  • Time Complexity: O( (N+M)! / (N! * M!) ) - Combinatorial explosion.
  • Space Complexity: O(N+M) for the recursion stack and string builder.
Author:
vicegd

  • Constructor Details

    • StringInterleavingGenerator

      public StringInterleavingGenerator()

  • Method Details

    • generateAllInterleavings

      public List<String> generateAllInterleavings(String a, String b)
      Generates all possible interleavings of two strings.
      Parameters:
      a - The first source string.
      b - The second source string.
      Returns:
      A list containing all valid interleavings.