Word Break

December 21, 2023

Problem #

Given a string s and a dictionary of words, determine if it’s possible to break s into one or more words from the dictionary. Return true if such a break is possible, false otherwise

Solution #

The Python function word_break successfully determines if a given string s can be segmented into one or more words from the provided dictionary. The function returns True if such a segmentation is possible, and False otherwise.

Here’s the code:

def word_break(s, word_dict):
    """
    Determine if the string s can be segmented into a space-separated sequence of one or more dictionary words.
    
    :param s: The input string
    :param word_dict: A set of words representing the dictionary
    :return: True if the string can be segmented, False otherwise
    """
    n = len(s)
    # dp[i] will be True if s[0:i] can be segmented
    dp = [False] * (n + 1)
    dp[0] = True  # Base case, empty string

    for i in range(1, n + 1):
        for j in range(i):
            # If s[0:j] can be segmented and s[j:i] is in the dictionary, then s[0:i] can be segmented
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True
                break

    return dp[n]

# Example usage
s = "crazycode"
word_dict = {"crazy", "code"}
result = word_break(s, word_dict)
print(result)

This code uses dynamic programming to solve the problem. It iterates through the string and checks if any substring of s can be formed using the words in the word_dict. The dp array is used to store whether the substring ending at each index can be segmented according to the dictionary. If the entire string s can be segmented, dp[n] (where n is the length of s) will be True.

In the provided example, the string "crazycode" can be segmented into the words "crazy" and "code", both of which are in the provided dictionary, so the function returns True.