Solving LeetCode Problem #139: Word Break Using Dynamic Programming

Introduction

In this post, we’ll delve into a fascinating dynamic programming problem — Word Break. This is LeetCode Problem #139 and it’s a fantastic problem to refine your dynamic programming skills.

Problem Statement

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

For example, if s = "leetcode" and wordDict = ["leet", "code"], the output would be true since "leetcode" can be segmented as "leet code".

Approach

To tackle this problem, we’ll use dynamic programming. The intuition is to break down the larger problem into subproblems, which in this case is checking if a substring of the given string can be segmented into a sequence of valid words.

Here are the steps:

1. Create a boolean DP array of size n+1, where n is the length of the string. dp[i] represents whether the string till the ith index can be segmented into dictionary words.
2. Initialize dp[0] = True since an empty string can always be segmented.
3. Nested loop: The outer loop traverses the dp array from 1 to n, and the inner loop checks each substring ending at the current index and starting anywhere before it.
4. If a substring is present in the word dictionary, and the remaining string before this substring (as indicated by dp[j]) can be segmented into valid words, then we can say that the string till the current index can be segmented into valid words.

Python Solution

Now, let’s see the Python code that implements this approach:

def wordBreak(s: str, wordDict: List[str]) -> bool:
    wordSet = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break
    return dp[-1]

Time and Space Complexity Analysis

The time complexity of this solution is O(n²), where n is the length of the input string. This is because in the worst-case scenario, we are checking every possible substring of the input string.

The space complexity is O(n), because we use a boolean array of size n+1 to keep track of subproblem solutions.

Conclusion

In summary, we solved the Word Break problem using dynamic programming by breaking the problem down into subproblems and solving it bottom-up. This problem is a great example of how dynamic programming can be used to solve complex problems with overlapping subproblems. So, keep practicing and happy coding!