Word Break medium

Problem Statement

Given a string s and a dictionary of strings wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example 1

Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".

Steps

1. Initialization: Create a dynamic programming table dp of boolean values, where dp[i] is true if the substring s[:i] can be segmented into words from wordDict, and false otherwise. Initialize dp[0] to True because an empty string can always be segmented.

2. Iteration: Iterate through the string s from index 1 to its length. For each index i, check if the substring s[:i] can be segmented. This is done by checking if there exists a j (0 < j <= i) such that:

   • dp[j] is true (meaning s[:j] can be segmented)
   • s[j:i] is in wordDict (meaning the remaining substring is a valid word).

3. Result: After iterating through the entire string, dp[len(s)] will indicate whether the entire string s can be segmented.

Explanation

The dynamic programming approach efficiently avoids redundant computations. By building up the solution from smaller substrings to larger ones, we only need to consider each substring once. The dp table stores the results of subproblems, allowing us to reuse them without recalculation. If a substring can be segmented, it means there exists a point within that substring where it can be split into two valid smaller segmented substrings.

Code

def wordBreak(s, wordDict):
    """
    Determines if a string can be segmented into words from a dictionary.

    Args:
        s: The input string.
        wordDict: A list of strings representing the dictionary.

    Returns:
        True if the string can be segmented, False otherwise.
    """
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string can always be segmented

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordDict:
                dp[i] = True
                break  # Once we find a valid segmentation, no need to check further

    return dp[n]

Complexity

• Time Complexity: O(n^2), where n is the length of the string s. The nested loops iterate through all possible substring combinations.
• Space Complexity: O(n), due to the dp table of size n+1.