1
class Solution:
2
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
3
        memo = {}
4

5
        def can_construct(target, strings_bank, memo):
6
            if target in memo:
7
                return memo[target]
8
            if target == "":
9
                return True
10
            for (
11
                element
12
            ) in (
13
                strings_bank
14
            ):  # for every element in our dict we check if we can start constructing the string "s"
15
                if (
16
                    element == target[0 : len(element)]
17
                ):  # the remaining of the string "s" (which is the suffix) is the new target
18
                    suffix = target[len(element) :]
19
                    if can_construct(suffix, strings_bank, memo):
20
                        memo[target] = True
21
                        return True
22
            memo[target] = False
23
            return False
24

25
        return can_construct(s, wordDict, memo)