Word Break

Given a non-empty string and a dictionary containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

A word may be reused multiple times in the segmentation.

Function Signature:

from typing import List

def word_break(s: str, wordDict: List[str]) -> bool:
    """
    Determine if the given string can be segmented into words from the dictionary.

    Parameters:
    - s: A non-empty string.
    - wordDict: List of non-empty words in the dictionary.

    Returns:
    - bool: True if s can be segmented, False otherwise.
    """
    # Your code here

Example:

# Input: s = "daynight", wordDict = ["day", "night"]
# Output: True
# Explanation: "daynight" can be segmented into "day" and "night".

# Input: s = "daynight", wordDict = ["day", "noon", "nigh"]
# Output: False
# Explanation: "daynight" cannot be segmented into words from the dictionary.

# Input: s = "applepenapple", wordDict = ["apple", "pen"]
# Output: True
# Explanation: "applepenapple" can be segmented into "apple" and "pen" or "applepen" and "apple".

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Instructions:

• Write the word_break function to solve the problem.
• Implement your solution in Python.
• Provide clear comments in your code.
• Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊