139. Word Break Medium

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

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet 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

Approach

Input: A string s and a string list wordDict.

Output: Determine whether this string can be segmented into one or more words from the dictionary string list.

This problem belongs to Linear DP problems.

Imagine you are reading string s, and as you go, you ask yourself: "When I reach here, can the previous segment be cut properly?"

Thus, we can use an array dp to keep track:

dp[i] = True signifies that s[0:i] (the first i characters) can be segmented.

Initialization: dp[0] = True (an empty string obviously counts as "segmentable").

Then we keep moving forward:

For every position i, check a previous index j. If dp[j] is True, and the substring s[j:i] is in the dictionary, then it means dp[i] = True.

Finally, checking dp[len(s)] tells us whether the entire string can be segmented.

Implementation

python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Convert wordDict to a set, enabling O(1) time complexity for substring containment checks
        wordDictSet = set(wordDict)
        n = len(s)

        # dp[i] represents whether s[:i] (the first i characters) can be segmented into words in the dictionary
        dp = [False] * (n + 1)

        # An empty string is considered validly segmented, acting as our base case
        dp[0] = True

        # Outer loop: i represents the first i characters
        for i in range(1, n + 1):
            # Inner loop: attempting all split points j
            # If s[:j] can be segmented, and the remaining substring s[j:i] is in the dictionary
            # Then s[:i] can also be segmented
            for j in range(i):
                if dp[j] and s[j:i] in wordDictSet:
                    dp[i] = True
                    break   # Break early since finding one valid segmentation is sufficient
         
        # Return whether the complete string can be segmented
        return dp[n]

javascript

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    // Convert the dictionary to a Set to improve lookup efficiency O(1)
    const wordSet = new Set(wordDict);

    // dp[i] represents whether s[0..i-1] can be segmented into dictionary words
    const dp = Array(s.length + 1).fill(false);

    // Empty string is trivially segmentable, serving as the starting point of inference
    dp[0] = true;

    // Outer loop: enumerates the end index i of substrings
    for (let i = 1; i < s.length + 1; i++) {
        // Inner loop: enumerates the cut point j
        // If s[0..j-1] is recursively segmentable, and s[j..i-1] is present in the Set
        // Then s[0..i-1] is completely segmentable
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.slice(j, i))) {
                dp[i] = true;
                break; // One valid segmentation approach is enough, break early
            }
        }
    }

    // Return whether the whole string sequence conforms
    return dp[s.length];
};

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Links

139. Word Break (English)

139. 单词拆分 (Chinese)