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"])
(target: str, word_bank: list[str] | None = None)
| 7 | |
| 8 | |
| 9 | def all_construct(target: str, word_bank: list[str] | None = None) -> list[list[str]]: |
| 10 | """ |
| 11 | returns the list containing all the possible |
| 12 | combinations a string(`target`) can be constructed from |
| 13 | the given list of substrings(`word_bank`) |
| 14 | |
| 15 | >>> all_construct("hello", ["he", "l", "o"]) |
| 16 | [['he', 'l', 'l', 'o']] |
| 17 | >>> all_construct("purple",["purp","p","ur","le","purpl"]) |
| 18 | [['purp', 'le'], ['p', 'ur', 'p', 'le']] |
| 19 | """ |
| 20 | |
| 21 | word_bank = word_bank or [] |
| 22 | # create a table |
| 23 | table_size: int = len(target) + 1 |
| 24 | |
| 25 | table: list[list[list[str]]] = [] |
| 26 | for _ in range(table_size): |
| 27 | table.append([]) |
| 28 | # seed value |
| 29 | table[0] = [[]] # because empty string has empty combination |
| 30 | |
| 31 | # iterate through the indices |
| 32 | for i in range(table_size): |
| 33 | # condition |
| 34 | if table[i] != []: |
| 35 | for word in word_bank: |
| 36 | # slice condition |
| 37 | if target[i : i + len(word)] == word: |
| 38 | new_combinations: list[list[str]] = [ |
| 39 | [word, *way] for way in table[i] |
| 40 | ] |
| 41 | # adds the word to every combination the current position holds |
| 42 | # now,push that combination to the table[i+len(word)] |
| 43 | table[i + len(word)] += new_combinations |
| 44 | |
| 45 | # combinations are in reverse order so reverse for better output |
| 46 | for combination in table[len(target)]: |
| 47 | combination.reverse() |
| 48 | |
| 49 | return table[len(target)] |
| 50 | |
| 51 | |
| 52 | if __name__ == "__main__": |
no test coverage detected