Word Break Leetcode Problem 139 [Python Solution]

Today, we’re diving into the Word Break problem, a fascinating challenge involving strings and dictionaries.

In this blog post, we’ll explore this problem step by step, optimizing our understanding for a beginner-friendly experience.

Problem Overview

The Word Break problem can be summarized as follows: Given a string s and a dictionary of strings wordDict, we aim to determine if it’s possible to segment s into space-separated sequences of words found in wordDict.

These words can be reused multiple times in the segmentation.

Example 1:

Let’s illustrate this with an example:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: We can segment “leetcode” as “leet code,” which are words in the dictionary.

Therefore, the output is true.

Understanding Constraints

Before we dive into solving the problem, let’s consider the constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings in wordDict are unique.

Now that we understand the problem, let’s explore two approaches to solving it: the Brute Force Approach and the Efficient Approach.

Brute Force Approach

The Brute Force Approach involves systematically checking different prefixes of the input string s to determine if they match words in the dictionary.

If we find a match, we proceed to the next segment of the string and continue this process.

However, this method can be inefficient, especially for large inputs, as it can result in a high number of recursive calls.

Pseudo-Code for Brute Force Approach

def wordBreak(s, wordDict):
    for i in range(len(s)):
        for w in wordDict:
            if s[i:i+len(w)] == w:
                # Found a match, continue with the rest of the string
                if wordBreak(s[i+len(w):], wordDict):
                    return True
    return False

This approach has a time complexity of O(n^2 * m), where n is the length of the input string s, and m is the number of words in the dictionary.

Efficient Approach

Instead of exhaustively checking all possible prefixes, we can optimize our approach by considering each word in the dictionary as a potential starting point in the string.

This approach has a time complexity of O(n * m).

Efficient Python Code Solution

Here’s a Python solution that implements the more efficient approach:

def wordBreak(s, wordDict):
    n = len(s)
    dp = [False] * (n + 1)
    dp[n] = True

    for i in range(n - 1, -1, -1):
        for w in wordDict:
            if i + len(w) <= n and s[i:i + len(w)] == w:
                dp[i] = dp[i + len(w)]
            if dp[i]:
                break

    return dp[0]

This dynamic programming solution leverages a bottom-up approach, efficiently tracking whether it’s possible to segment the string into valid words.

Time and Space Complexity

The efficient approach has a time complexity of O(n * m) and a space complexity of O(n), making it a more practical solution for larger inputs.

Reasoning Behind Our Approach

The key to this efficient approach lies in considering each word in the dictionary as a potential starting point for word segmentation.

By building a dynamic programming table, we can efficiently track the possibilities and identify valid segmentations.

Related Interview Questions By Company:

• Construct Binary Tree From Preorder And Inorder Traversal LeetCode
• Interleaving String LeetCode
• Validate Binary Search Tree LeetCode

Related Interview Questions By Difficulty:

• House Robber LeetCode
• Partition Equal Subset Sum LeetCode
• Climbing Stairs LeetCode

Related Interview Questions By Category:

• Can Place Flowers LeetCode
• Best Time To Buy And Sell Stock With Cooldown LeetCode
• Course Schedule II LeetCode

Conclusion

In this blog post, we delved into the Word Break problem, exploring both brute force and efficient approaches to tackle it.

We learned that the efficient approach, based on dynamic programming, offers a more practical solution for larger inputs.

We hope this guide has been valuable to you, especially if you’re new to coding or tackling dynamic programming problems.

If you found this content helpful, please consider liking and subscribing to support our our platform.

If you have questions or suggestions, feel free to leave a comment.

Happy coding!

Link to the Word Break problem on LeetCode