Word Break

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:

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.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

bool wordBreak(string s, vector<string> &w)
{
    int n = s.length();
    unordered_set<string> m(w.begin(), w.end());
    int dp[n + 1];
    memset(dp, 0, sizeof dp);
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        string t = "";
        for (int j = i; j < n; j++)
        {
            t += s[j];
            if (m.find(t) != m.end())
            {
                if (dp[j + 1] == 1)
                {
                    dp[i] = 1;
                }
            }
        }
    }
    return dp[0];
}

int main()
{
    string s = "applepenapple";
    vector<string> wordDict = {"apple", "pen"};

    if (wordBreak(s, wordDict))
        cout << "true";
    else
        cout << "false";

    return 0;
}