How to solve Word Break problem in LeetCode 139 efficiently?

本文共计315个文字，预计阅读时间需要2分钟。

LeetCode 139. Word Break - 我使用的解法是区间DP + class Solutioncpppublic: map m; int dp[1005][1005];

bool wordBreak(string s, vector& wordDict) { for (int i=0; i

bool wordBreakHelper(string s, int start, int end) { if (start > end) return false; if (start==end) return m.count(s.substr(start, end - start + 1)); if (dp[start][end] !=0) return dp[start][end]==1;

for (int i=start; i <=end; i++) { if (m.count(s.substr(start, i - start + 1)) && wordBreakHelper(s, i + 1, end)) return dp[start][end]=1; } return dp[start][end]=0; }

​​LeetCode 139. Word Break​​

我使用的方法是区间DP

class Solution {
public:
map<string,int> m;
int dp[1005][1005];
bool wordBreak(string s, vector<string>& wordDict) {

for(int i=0;i<wordDict.size();i++)
m[wordDict[i]]=1;
memset(dp,0,sizeof(dp));
fun(s);
if(dp[0][s.length()-1]==1)
return true;
else
return false;

}

void fun(string s)
{
int len=s.length();
for(int l=1;l<=len;l++)
{
for(int i=0;i+l-1<len;i++)
{
int j=i+l-1;
string s1 = s.substr(i,l);
if(m[s1]==1)
dp[i][j]=1;
else{
for(int k=i;k<j;k++)
{
if(dp[i][k]==1&&dp[k+1][j]==1)
dp[i][j]=1;
}
}
}
}
}
};