algoadvance

Leetcode 139. Word Break

Problem Statement

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.

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

Example 3:

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

Clarifying Questions

1. Does the function need to handle empty strings?
   • If s is an empty string, should we return true as it can be seen as being segmented into zero words?
2. Can the wordDict contain duplicate words?
   • Yes, but they should be considered as unique.
3. Should we consider case sensitivity?
   • Yes, both s and words in wordDict are case-sensitive.

Strategy

To solve this problem, we can use dynamic programming. We’ll maintain a boolean array dp where dp[i] will be true if the substring s[0..i-1] can be segmented into words found in wordDict.

Steps:

1. Initialize dp[0] to true since the empty string can always be segmented trivially.
2. Iterate through the string s with an outer loop, and for each character position, use an inner loop to check all substrings ending at that position.
3. If a valid substring is found, update the corresponding dp array element.
4. The answer will be in dp[s.length()].

Code

#include <vector>
#include <string>
#include <unordered_set>

class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        std::unordered_set<std::string> wordSet(wordDict.begin(), wordDict.end());
        std::vector<bool> dp(s.size() + 1, false);
        dp[0] = true; // Empty string is a valid segmentation

        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};

Time Complexity

• Time Complexity: O(n^2 * m), where n is the length of the string s and m is the maximum length of the words in wordDict. The nested loops imply O(n^2) and checking each substring against the set takes O(m) time in the worst case.
• Space Complexity: O(n), for the dp array of size n+1, along with the space required for the unordered_set.

The provided implementation efficiently uses dynamic programming to determine whether the input string s can be segmented according to the provided word dictionary.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?