Leecode 1593. 拆分字符串使唯一子字符串的数目最大 DFS+回溯+剪枝

原题链接: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;
    }
};

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
青葱年少的头像青葱年少普通用户
上一篇 2022年5月11日
下一篇 2022年5月11日

相关推荐