leetcode139. 单词拆分

dp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int m=s.size();
        vector<bool>f(m+1,false);
        f[0]=true;
        for(int i=0;i<=m;i++){
            for(auto w:wordDict){
                int len=w.size();
                if(i>=len&&s.substr(i-len,len)==w){
                    f[i]=f[i]||f[i-len];
                }
            }
        }
        return f[m];
    }
};