We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Word Break

Number: 139

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Microsoft, TikTok, Bloomberg, Walmart Labs, Intuit, MongoDB, BuyHatke, Netflix, Salesforce, Grammarly, LinkedIn, Nutanix, Apple, Oracle, Adobe, Tesla, Uber, eBay, Coupang, Zoho, Flipkart, Netskope, Palo Alto Networks, Pocket Gems, Yahoo, Block

Problem Description

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. Note that each word in wordDict can be used multiple times.

Key Insights

  • Use Dynamic Programming (DP) to break the problem into subproblems.
  • Create a DP array where dp[i] is true if the substring s[0:i] can be segmented using words from the dictionary.
  • Leverage a hash set for fast look-up of dictionary words.
  • For every index i, check all possible previous break points j such that dp[j] is true and s[j:i] is in the wordDict.
  • The problem can also be approached with recursion and memoization, but DP is more straightforward for iterative implementation.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario, where n is the length of s (each substring check is O(1) if using a hash set, and there could be O(n^2) checks overall). Space Complexity: O(n) for the dp array and O(k) for the hash set where k is the number of words in the dictionary.

Solution

The solution uses a Dynamic Programming (DP) approach:

  1. Convert wordDict to a hash set for constant time lookup.
  2. Create a boolean dp array of size n+1 (n is the length of s), where dp[i] indicates if s[0:i] can be segmented.
  3. Set dp[0] to true because an empty string is always segmentable.
  4. For each index i from 1 to n, iterate through all indices j from 0 to i:
    • If dp[j] is true and the substring s[j:i] is in the dictionary, then set dp[i] to true.
    • Break early from the inner loop when a valid break is found.
  5. Return dp[n] as the result.

This method efficiently builds up the solution by utilizing previous results to determine if the entire string can be segmented.

Code Solutions

# Python solution for the Word Break problem

def wordBreak(s, wordDict):
    # Convert the list to a set for O(1) look-ups
    wordSet = set(wordDict)
    
    # dp[i] is True if s[0:i] can be segmented into words from the wordDict
    n = len(s)
    dp = [False] * (n + 1)
    
    # Base case: empty string is always segmentable
    dp[0] = True

    # Iterate through the string positions
    for i in range(1, n + 1):
        # Check every possible partition s[0:j] and s[j:i]
        for j in range(i):
            # If s[0:j] can be segmented and s[j:i] is in the dictionary
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True  # s[0:i] can be segmented
                break  # No need to check further partitions
    return dp[n]

# Example usage:
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict))  # Output: True
← Back to All Questions