Word Break

Problem Statement

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words.

You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique.

Example 1:

Input: s = "pythoncode", wordDict = ["python","code"]

Output: true

Explanation: Return true because “pythoncode” can be split into “python” and “code”.

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen","ape"]

Output: true

Explanation: Return true because “applepenapple” can be split into “apple”, “pen” and “apple”. Notice that we can reuse words and also not use all the words.

Example 3:

Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]

Output: false

Constraints:

• 1 <= s.length <= 200
• 1 <= wordDict.length <= 100
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.

Recommended Time and Space Complexity

You should aim for a solution with O(n * m * t) time and O(n) space, where n is the length of the string s, m is the number of words in wordDict and t is the maximum length of any word in wordDict.

Hint 1

Consider using recursion to solve this problem. Can you define a recursive function that checks if a substring of s can be segmented into dictionary words?

Hint 2

Memoization can be used to optimize the recursive solution. Store the results of the recursive calls to avoid redundant computations.

Hint 3

Dynamic programming can be used to solve this problem in a bottom-up manner. Create a boolean array dp where dp[i] is true if the substring s[0...i] can be segmented into dictionary words.

Solution

name: Word Break - Recursion

def word_break(s: str, word_dict: List[str]) -> bool:
    def dfs(i):
        if i == len(s):
            return True

        for w in word_dict:
            if ((i + len(w)) <= len(s) and
                    s[i : i + len(w)] == w
            ):
                if dfs(i + len(w)):
                    return True
        return False

    return dfs(0)

Time & Space Complexity

• Time complexity: O(t * m ^ n)
• Space complexity: O(n)

Where n is the length of the string s, m is the number of words in wordDict and t is the maximum length of any word in wordDict.