Word Break: Segmenting Strings with a Dictionary

Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. This problem is fundamental in natural language processing and text analysis, where understanding the structure and meaning of sentences often relies on breaking them down into meaningful units.

Problem Description

You are tasked with creating a function that takes a non-empty string s and a list of non-empty words wordDict as input. Your goal is to ascertain whether s can be formed by concatenating words from wordDict. Each word in wordDict can be used multiple times.

Key Requirements:

• The function should return a boolean value: TRUE if s can be segmented, and FALSE otherwise.
• All words in wordDict are unique.
• The segmentation must cover the entire string s.

Expected Behavior:

If s can be broken down into a sequence of words from wordDict, the function should return TRUE. For instance, if s is "leetcode" and wordDict contains ["leet", "code"], the function should return TRUE because "leetcode" can be segmented as "leet code".

Edge Cases:

• An empty wordDict.
• A string s that cannot be formed by any combination of words in wordDict.
• A string s that is itself present in wordDict.

Examples

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: TRUE
Explanation: "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: TRUE
Explanation: "applepenapple" can be segmented as "apple pen apple".
Note that "apple" can be reused.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: FALSE
Explanation: There is no way to segment "catsandog" using the provided dictionary.

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 of wordDict are unique.

Notes

Consider how you might efficiently check if a substring of s exists within wordDict. Dynamic programming or recursion with memoization are common approaches for this type of problem. Think about breaking down the problem into smaller subproblems: can a prefix of s be segmented?