原题链接:Leecode 1593. 拆分字符串使唯一子字符串的数目最大
class Solution {
public:
map<string,int> vis;
int res=0;
void dfs(string s,int i,int sum)
{
if(i==s.size())
{
res=max(res,sum);
return ;
}
//剪枝 如果当前情况不论怎么拆分,得到子字符串都比已知的长度要小
if(sum+s.size()-i<res) return ;
for(int j=i;j<s.size();j++)
{
string t=s.substr(i,j-i+1);
if(!vis[t])
{
vis[t]=1;
dfs(s,j+1,sum+1);
vis[t]=0;
}
}
}
int maxUniqueSplit(string s) {
dfs(s,0,0);
return res;
}
};
文章出处登录后可见!
已经登录?立即刷新