FilesExpand file tree

master

/

all_construct.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (49 loc) · 1.94 KB

master

/

all_construct.py

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (49 loc) · 1.94 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

"""

Program to list all the ways a target string can be

constructed from the given list of substrings

"""

from __future__ import annotations

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

"""

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']]

"""

word_bank = word_bank or []

# create a table

table_size: int = len(target) + 1

table: list[list[list[str]]] = []

for _ in range(table_size):

table.append([])

# seed value

table[0] = [[]] # because empty string has empty combination

# iterate through the indices

for i in range(table_size):

# condition

if table[i] != []:

for word in word_bank:

# slice condition

if target[i : i + len(word)] == word:

new_combinations: list[list[str]] = [

[word, *way] for way in table[i]

]

# adds the word to every combination the current position holds

# now,push that combination to the table[i+len(word)]

table[i + len(word)] += new_combinations

# combinations are in reverse order so reverse for better output

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"],

)

)