第二题和leetcode139很像的链接为：https://leetcode-cn.com/problems/word-break/
注意到第二题的数据范围为字符串的长度<=50000,如果单纯使用力扣代码，此时的复杂度为o(n^2），可以达到10^10级别，那么肯定无法AC。
那么考虑到给定的一个条件：可划分的字符串长度<=20。可以考虑去做一步优化，从当前位置的前20开始查起，然后去做。优化代码为:
#include<bits/stdc++.h>
using namespace std;
int main(){
const int num=1e9+7;
unordered_map<string,bool>m;
string str;
cin>>str;
int N;
cin>>N;
while(N--){
string tmp;
cin>>tmp;
m[tmp]=true;
}
int n=str.size();
vector<int>dp(n+1,0);
dp[0]=1;
for(int i=0;i<n;i++){
for(int j=max(0,i-19);j<=i;j++){
string tmp=str.substr(j,i-j+1);
if(m[tmp]){
dp[i+1]=(dp[i+1])%num+(dp[j]%num);
}
}
}
cout<<dp[n]<<endl;
return 0;
}
这样的话可以过0.7，依旧无法AC。
但是考虑到状态转移中，当前状态最多与前20个状态有关系，我们可以对状态做一步缩小化：
#include<bits/stdc++.h>
using namespace std;
int main(){
const int num=1e9+7;
unordered_map<string,bool>m;
string str;
cin>>str;
int N;
cin>>N;
while(N--){
string tmp;
cin>>tmp;
m[tmp]=true;
}
int n=str.size();
vector<int>dp(21,0);
dp[0]=1;
for(int i=0;i<n;i++){
for(int j=max(0,i-19);j<=i;j++){
string tmp=str.substr(j,i-j+1);
if(m[tmp]){
int t1=((i+1))%20;
int t2=(j%20);
dp[t1]=(dp[t1])%num+(dp[t2]%num);
}
}
}
cout<<dp[n%20]<<endl;
return 0;
}
这样整体来看的化，空间缩小了，也许能AC。但是考试的时候自己是按照第一份代码做的，所以只过了0.7。
当然这些只是自己的一些看法，欢迎大家讨论。
全部评论
(2) 回帖