dp思想

dp[i] // 表示 [0, i) 是否已经匹配

所以 对于( j < i && dp[j] && wordDict.contains(s.substr(j, i-j)) ) dp[i]是匹配的因为 [0,j-1]已经匹配了  然后从[j, i-1] 也已经匹配了 所以 dp[i] = true

code

class Solution {public:    bool wordBreak(string s, vector
    
     & wordDict) {        int len = s.size();        if(len == 0 && wordDict.size() == 0)            return true;        if(len == 0 || wordDict.size() == 0)            return false;        unordered_map
     
       mp;        for(auto x : wordDict) mp[x] = true;        vector
      
        dp(len+1, false);        dp[0] = true;        for(int i=1; i<=len; i++) {            for(int j=0; j