Word Break

Problem

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.

Solution Approach

Expected Time complexity: $O(n^3)$

Click - to see solution code

C++

class Solution {
   public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, int> mp;
        for (auto i : wordDict) mp[i] = 1;

        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                string w = s.substr(j, i - j);
                if (mp.find(w) != mp.end() && dp[j]) dp[i] = true;
            }
        }

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