algoadvance

Given a string s and a dictionary of strings wordDict, 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: Return true because "leetcode" can be segmented as "leet code".

Example:

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 dictionary words.

Example:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Clarifying Questions

1. Can the dictionary contain repeated words?
   • The dictionary typically does not contain repeated words, as they won’t affect the solution.
2. Is the dictionary case-sensitive?
   • Yes, assume that the dictionary is case-sensitive.
3. Are there any limits on the length of the string or the dictionary?
   • Typically, constraints will be such that a reasonable algorithm can solve it in time.
4. Can the string s be empty? What should be the output for an empty string with any dictionary?
   • Yes, the string s can be empty. If s is empty, the output should be true since it trivially satisfies the condition.

Strategy

We can use dynamic programming to solve this problem. Let’s define a boolean array dp where dp[i] will be True if the substring s[:i] can be segmented into words from the dictionary and False otherwise.

The steps are:

1. Initialization: Set dp[0] = True, meaning that an empty string can always be segmented.
2. Filling the dp array: For every position i in the string from 1 to len(s), check every possible substring s[j:i] where 0 <= j < i. If dp[j] is True and the substring s[j:i] is in wordDict, then set dp[i] to True.

Finally, return dp[-1], which tells if the entire string can be segmented.

Code

def wordBreak(s: str, wordDict: list) -> bool:
    word_set = set(wordDict)  # Convert list to set for O(1) lookups
    dp = [False] * (len(s) + 1)
    dp[0] = True  # Base case: empty string

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[-1]

# Example test cases
print(wordBreak("leetcode", ["leet", "code"]))  # Output: True
print(wordBreak("applepenapple", ["apple", "pen"]))  # Output: True
print(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))  # Output: False

Time Complexity

The time complexity of this approach is O(n^2 * m):

• n is the length of the string s.

• m is the maximum length of a single word in wordDict.

• There are n iterations for the outer loop.
• For each i, the inner loop runs i times, resulting in O(n^2) iterations.
• Checking if a substring is in the set wordDict takes O(m) in the worst case.

So overall, the complexity is O(n^2 * m). The space complexity is O(n) due to the dp array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?