Introduction

In the realm of dynamic programming, the Word Break Problem stands out as an intriguing challenge that often appears in coding interviews. The problem is to decide if a given string can be segmented into a space-separated sequence of one or more dictionary words. Before we dive into the dynamic programming approach, let's set the stage with some examples.

Problem Statement

Given a string s and a list of strings (a dictionary) wordDict, you need to determine if s can be segmented into words found in wordDict.

Examples

1. Input:
   s = "leetcode"
wordDict = ["leet", "code"]
   Output:
   True
   Explanation:
   The string "leetcode" can be broken down into "leet" + "code".

2. Input:
   s = "applepenapple"
wordDict = ["apple", "pen"]
   Output:
   True
   Explanation:
   The string can be segmented as "apple" + "pen" + "apple".

3. Input:
   s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
   Output:
   False
   Explanation:
   There is no valid segmentation for the string "catsandog".

Dynamic Programming Approach

Dynamic programming is an efficient way to tackle this problem by breaking it down into simpler subproblems. The idea is to maintain a boolean array dp where dp[i] will be True if the substring s[0:i] can be segmented into words from wordDict.

Step-by-Step Explanation

1. Initialization:
   Create a boolean array dp of size len(s) + 1, initialized to False. Set dp[0] = True, as an empty string can always be segmented.

2. Iterate Through the String:
   For each index i from 1 to len(s), check every index j from 0 to i - 1. If dp[j] is True and the substring s[j:i] exists in wordDict, set dp[i] to True.

3. Final Result:
   The value of dp[len(s)] will indicate whether the entire string can be segmented.

Pseudocode

Here's a breakdown of the pseudocode to implement 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[len(s)]

Example Walkthrough

Let’s evaluate s = "leetcode" with wordDict = ["leet", "code"]:

• Initialization:
  dp = [True, False, False, False, False, False, False, False, False]

• Index 1:

  • j = 0:
    dp[0] is True, but "l" is not in wordDict.
  • Move to index 2, not updating dp[1].

• Index 2:

  • j = 0:
    dp[0] is True, but "le" is not in wordDict.
  • j = 1:
    dp[1] is False, skip it.
  • Move to index 3, dp[2] remains False.

• Index 3:

  • j = 0:
    "lee" is not in wordDict.
  • Apply similar checks until index 4.
  • At i=4:
    • j=0: "leet" in wordDict, so dp[4] = True.

Following this logic through to i=8, we find that dp[len(s)] is True.

Complexity Analysis

• Time Complexity:
  The time complexity for this approach is O(n^2), where n is the length of the string. This is due to the two nested loops traversing the string.

• Space Complexity:
  The space complexity is O(n) for the dp array.

By employing a dynamic programming solution, you can handle larger strings and dictionaries efficiently, gaining proficiency in this essential problem-solving technique.