Back to solutions

Word Break

MediumDynamic Programming

Return true if s can be segmented into a space-separated sequence of dictionary words.

Open problem
Constraints
  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000

DP over prefixes

Time O(n^2)Space O(n)

dp[i] is true if the first i characters can be segmented. For each i, check every split point j where dp[j] is true and s[j..i) is a dictionary word.

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

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; }
    return dp[n];
}