Word Break

Problem Statement

In this task, we are provided with two main inputs: a string s and a list of strings called wordDict. The objective is to determine whether the string s can be completely segmented into a sequence of one or more words that exactly match the words found in wordDict.

Key rules:

• Words from the wordDict can be used multiple times.
• The order of segments in s must exactly form the original string.
• The complete string s must be used up by concatenating whole words from wordDict.

Return true if such segmentation is possible and false otherwise.

Examples

Example 1

Input:

s = "vultrcode", wordDict = ["vultr","code"]

Output:

true

Explanation:

Return true because "vultrcode" can be segmented as "vultr code".

Example 2

Input:

s = "applepenapple", wordDict = ["apple","pen"]

Output:

true

Explanation:

Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3

Input:

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Output:

false

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

Approach and Intuition

This problem is a classic case for Dynamic Programming. We'll define a boolean DP array dp where:

• dp[i] is true if the substring s[0:i] can be formed by concatenating words in wordDict.
• dp[0] is initialized as true because an empty string is trivially valid.

Implementation Steps:

1. Initialize dp = [False] * (len(s) + 1), and set dp[0] = True.

2. For every index i from 1 to len(s):

   • For each word in wordDict, check:

     • If s[i-len(word):i] == word and dp[i-len(word)] == True, then set dp[i] = True.

3. Return dp[len(s)].

This solution runs in O(n × k) time, where n = len(s) and k is the total number of characters across all words in wordDict.

Example Walkthrough

For s = "vultrcode" and wordDict = ["vultr", "code"]:

dp[5] = True because "vultr" ∈ wordDict
Then, since dp[5] = True and s[5:9] = "code" ∈ wordDict → dp[9] = True
Final result → dp[9] = True

For s = "catsandog" and wordDict = ["cats", "dog", "sand", "and", "cat"]:

Multiple segments are valid up to "cats" or "cat", "sand", and "and"
However, "og" at the end does not match any wordDict entry after valid prefix segments
Final result → False

This strategy ensures optimal performance while respecting the constraints.

Solutions

class Solution {
public:
    bool canSegmentString(string s, vector<string>& dict) {
        unordered_set<string> wordSet(dict.begin(), dict.end());
        vector<bool> canBreak(s.length() + 1, false);
        canBreak[0] = true;
            
        for (int end = 1; end <= s.length(); end++) {
            for (int start = 0; start < end; start++) {
                if (canBreak[start] && wordSet.find(s.substr(start, end - start)) != wordSet.end()) {
                    canBreak[end] = true;
                    break;
                }
            }
        }
            
        return canBreak[s.length()];
    }
};