139-单词拆分

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int length = s.size(); // dp[i]表示字符串 s 的前 i 个字符能否拆分成 wordDict vector<bool>dp(length + 1); dp[0] = true; for (int i = 0; i < s.size(); i++) { if (dp[i]) { for (string &str : wordDict) { if (i + str.size() <= length && str == s.substr(i, str.size())) { dp[i + str.size()] = true; } } } } return dp[length]; } };