139. Word Break

📝 Problem Details

• Title: 139. Word Break
• Link: https://leetcode.com/problems/word-break/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

input string s input vector of strings wordDict representing a dictionary of strings return true if s can be segmented into a space-separated sequence of one or more dictionary words

the same word in the dictionary can be reused multiple times in the segment

💭What Were My Initial Thoughts?

1. can it be broken up into a subproblem?
- we need to check if string s can be split into words from wordDict
- suggests a subproblem structure (check if smaller substrings of s can be segmented)

2. top-down vs bottom-up
- can do both but a bottom up approach would be more efficient

3. state definition
- let dp[i] = True if s[0:i] can be split into words from wordDict
- base case: dp[0] = True (empty string is always valid)

4. state transition
if dp[j] is true and s[j:i] is in wordDict, then dp[i] = True

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n+1, false);
        dp[0] = true; // base case --> empty string
 
        for(int i=1; i <= n; i++) { // iterate over string
            for(int j=0; j < i; j++) { //check all partitions
                if(dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break; // no need to check further
                }
            }
        }
        return dp[n]; // answer for full string
    }
};