1593. 拆分字符串使唯一子字符串的数目最大

1593. 拆分字符串使唯一子字符串的数目最大

s的长度最大只有15。直接暴力回溯就行。
另：看好题。必须要求唯一

class Solution {
public:
    int res = 0;
    unordered_set<string>st;
    int maxUniqueSplit(string s) {
        dfs(0, s);
        return res;
    }

    void dfs(int s,  string str) {
        if (s >= str.size()) {
            res = max(res, (int) st.size());
            return;
        }
        for (int i = s; i < str.size(); i++) {
            string tmp = str.substr(s, i - s + 1);
            if (!st.count(tmp)) {
                st.insert(tmp);
                dfs(i + 1, str);
                st.erase(tmp);
            }
        }
    }
};