Leetcode 1593. Split a String Into the Max Number of Unique Substrings(python)

题目

解法：暴力backtracking

因为要unique，所以dp不太做得了

class Solution:def maxUniqueSplit(self, s: str) -> int:def backtracking(ind):nonlocal ansif ind==len(s):ans = max(ans,len(split))for i in range(ind,len(s)):if s[ind:i+1] not in split:split.add(s[ind:i+1])backtracking(i+1)split.remove(s[ind:i+1])ans = 0split = set()backtracking(0)return ans

c++版本

class Solution {
    int max_split = 1;
public:void bt(string s,unordered_set<string>& seen,int split){
    if(s.size() == 0) max_split = max(max_split,split);for(int i=1;i<s.size()+1;i++){
    string tmp_s = s.substr(0,i);if(seen.count(tmp_s)) continue;seen.insert(tmp_s);bt(s.substr(i),seen,split+1);seen.erase(tmp_s);}}int maxUniqueSplit(string s) {
    unordered_set<string> seen;bt(s,seen,0);return max_split;}
};

不用global variable的版本

class Solution {
    int max_split = 1;
public:int bt(string s,unordered_set<string>& seen,int split){
    if(s.size() == 0) return 0;int res = 0;for(int i=1;i<s.size()+1;i++){
    string tmp_s = s.substr(0,i);if(seen.count(tmp_s)) continue;seen.insert(tmp_s);res = max(res, 1+bt(s.substr(i),seen,split+1));seen.erase(tmp_s);}return res;}int maxUniqueSplit(string s) {
    unordered_set<string> seen;return bt(s,seen,0);}
};

时间复杂度：O(2^n),n为字符串长度
空间复杂度：O(n)