Word Break Problem: A Dynamic Programming Approach

The "Word Break" problem is a popular question in dynamic programming. It involves determining whether a given string can be segmented into a sequence of one or more dictionary words.

Problem Statement

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

Example

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

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

Dynamic Programming Solution

function wordBreak(s, wordDict) {
  let wordSet = new Set(wordDict);
  let dp = new Array(s.length + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[s.length];
}

Breaking Down the Solution

• Initialize dp Array: Create an array dp of length s.length + 1 and initialize all elements to false, except dp[0], which is true.
• Dynamic Programming Iteration: Iterate through the string s. For each position i, check all substrings ending at i. If any substring is found in wordDict and the remaining part of the string up to the start of the substring is also breakable (as indicated by dp), mark dp[i] as true.
• Check for Word Break: Return the value of dp[s.length]. If it's true, it means the string s can be segmented into words from the dictionary.

Conclusion

The Word Break problem is an excellent application of dynamic programming to solve string manipulation challenges. It shows how problems can be solved by breaking them down into smaller, more manageable subproblems, and then combining these solutions to solve the larger problem.