def word_break(s, wordDict):
    dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for w in wordDict:
            j = i - len(w)
            if j >= 0 and dp[j] and s[j:i] == w:
                dp[i] = True
                break
    return dp[-1]


if __name__ == "__main__":
    print(word_break("applepenapple", ["apple", "pen"]))
    print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))