Leetcode 139. 单词拆分 动态规划

原题链接：Leetcode 139. 单词拆分

递归，超时

class Solution {
public:bool isfind(string s,map<string,int>& mp){for(auto x:mp){string word=x.first;if(s==word) return true;int n=word.size();if(n>s.size()) continue;string s1=s.substr(0,n);if(s1==word){string s2=s.substr(n);if(isfind(s2,mp)){mp[s2]=1; return true;}} string s3=s.substr(s.size()-n);if(s3==word){string s4=s.substr(0,s.size()-n);if(isfind(s4,mp)){mp[s4]=1; return true;}}}return false;}bool wordBreak(string s, vector<string>& wordDict) {map<string,int> mp;for(auto word:wordDict){if(s==word) return true;mp[word]=1;}return isfind(s,mp);}};

动态规划

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {map<string, int> mp;for (auto word : wordDict) {if (s == word)return true;mp[word] = 1;}int n = s.size();int dp[n + 1];for (int i = 1; i <= n; i++) {dp[i] = 0;for (int j = 0; j < i; j++) {string word = s.substr(j, i - j);if (dp[j] && mp[word] == 1) {dp[i] = 1;continue;}}}return dp[n];}
};