program to list all the ways a target string can be constructed from the given list of substrings returns the list containing all the possible combinations a stringtarget can be constructed from the given list of substringswordbank allconstructhello he l o he l l o allconstructpurple purp p ur le purpl purp le p ur p le create a table seed value iterate through the indices condition slice condition adds the word to every combination the current position holds now push that combination to the tableilenword combinations are in reverse order so reverse for better output returns the list containing all the possible combinations a string target can be constructed from the given list of substrings word_bank all_construct hello he l o he l l o all_construct purple purp p ur le purpl purp le p ur p le create a table seed value because empty string has empty combination iterate through the indices condition slice condition adds the word to every combination the current position holds now push that combination to the table i len word combinations are in reverse order so reverse for better output
from __future__ import annotations


def all_construct(target: str, word_bank: list[str] | None = None) -> list[list[str]]:
    

    word_bank = word_bank or []
    
    table_size: int = len(target) + 1

    table: list[list[list[str]]] = []
    for _ in range(table_size):
        table.append([])
    
    table[0] = [[]]  

    
    for i in range(table_size):
        
        if table[i] != []:
            for word in word_bank:
                
                if target[i : i + len(word)] == word:
                    new_combinations: list[list[str]] = [
                        [word, *way] for way in table[i]
                    ]
                    
                    
                    table[i + len(word)] += new_combinations

    
    for combination in table[len(target)]:
        combination.reverse()

    return table[len(target)]


if __name__ == "__main__":
    print(all_construct("jwajalapa", ["jwa", "j", "w", "a", "la", "lapa"]))
    print(all_construct("rajamati", ["s", "raj", "amat", "raja", "ma", "i", "t"]))
    print(
        all_construct(
            "hexagonosaurus",
            ["h", "ex", "hex", "ag", "ago", "ru", "auru", "rus", "go", "no", "o", "s"],
        )
    )