Description Link to heading

139.word-break

Solution Link to heading

First, we should determine what dp array means. In this problem, dp[i] = 1 denotes that a string of length i can be split into words that appear in the dictionary.

So, we can get the recursive relationship:dp[j] = dp[i] && substr in [i, j) can be split.

To initialize dp array: dp[0] = 1.

Attention: we should traverse volume first, then traverse items; if in the reverse order, it’s not convenient to judge whether string can be split.

Code Link to heading 

#include <string>
#include <unordered_set>
#include <vector>
using std::string;
using std::unordered_set;
using std::vector;
class Solution {
  public:
    bool wordBreak(string s, vector<string> &wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> dp(s.length() + 1, 0); // 0 means false
        dp[0] = 1;
        // traverse volume first, then items
        for (int j = 0; j <= s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                string word = s.substr(i, j - i);
                if (wordSet.find(word) != wordSet.end() && dp[i])
                    dp[j] = 1;
            }
        }
        return dp[s.size()];
    }
};