class Solution {
public:
int maxUniqueSplit(string s) {
}
};
1593. 拆分字符串使唯一子字符串的数目最大
给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：s = "ababccc" 输出：5 解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，因为其中的 'a' 和 'b' 都出现了不止一次。
示例 2：
输入：s = "aba" 输出：2 解释：一种最大拆分方法为 ['a', 'ba'] 。
示例 3：
输入：s = "aa" 输出：1 解释：无法进一步拆分字符串。
提示：
1 <= s.length <= 16
s 仅包含小写英文字母
原站题解
python3 解法, 执行用时: 292 ms, 内存消耗: 15 MB, 提交时间: 2022-12-09 16:27:23
class Solution:
def maxUniqueSplit(self, s: str) -> int:
# corner case
if len(s) == 1:
return 1
# dfs
def dfs(i, path):
if i == n:
if len(path) > self.res:
self.res = len(path)
return
for j in range(i, n):
if s[i:j + 1] not in path:
path.add(s[i:j + 1])
dfs(j + 1, path)
path.discard(s[i:j + 1])
return
self.res = float('-inf')
n = len(s)
dfs(0, set()) # 从0开始，到j-1为止
return self.res
python3 解法, 执行用时: 692 ms, 内存消耗: 156.3 MB, 提交时间: 2022-12-09 16:26:45
class Solution:
def maxUniqueSplit(self, s: str) -> int:
n = len(s)
@functools.lru_cache(None)
def dp(cur: int, ss: str):
if cur == n-1:
return len(set(ss.split()))
cur += 1
return max(dp(cur, ss + s[cur]), dp(cur, ss + ' ' + s[cur]))
return dp(0, s[0])
cpp 解法, 执行用时: 20 ms, 内存消耗: 8.8 MB, 提交时间: 2022-12-09 16:25:51
class Solution {
public:
int maxUniqueSplit(string s) {
dfs(s, 0);
return ans;
}
void dfs(string& s, int pos) {
if (s.size() - pos + us.size() <= ans) return;
if (pos == s.size()) {
ans = max(ans, (int)us.size());
return;
}
string temp;
for (int i = pos; i < s.size(); i++) {
temp += s[i];
if (us.find(temp) == us.end()) {
us.insert(temp);
dfs(s, i + 1);
us.erase(temp);
}
}
}
private:
int ans = 0;
unordered_set<string> us;
};
java 解法, 执行用时: 30 ms, 内存消耗: 41.7 MB, 提交时间: 2022-12-09 16:25:25
/**
* 拆分给定的字符串，要求拆分后的每个子字符串唯一，求子字符串的最大数目，可以通过回溯算法实现。
* 对于长度为 n 的字符串，有 n−1 个拆分点。从左到右遍历字符串，对于每个拆分点，如果在此拆分之后，
* 新得到的一个非空子字符串（即拆分点左侧的最后一个被拆分出的非空子字符串）与之前拆分出的非空子字符串都不相同，
* 则当前的拆分点可以进行拆分，然后继续对剩下的部分（即拆分点右侧的部分）进行拆分。
* 判断拆分出的非空子字符串是否有重复时，可以使用哈希表。
* 当整个字符串拆分完毕时，计算拆分得到的非空子字符串的数目，并更新最大数目。
**/
class Solution {
int maxSplit = 1;
public int maxUniqueSplit(String s) {
Set<String> set = new HashSet<String>();
backtrack(0, 0, s, set);
return maxSplit;
}
public void backtrack(int index, int split, String s, Set<String> set) {
int length = s.length();
if (index >= length) {
maxSplit = Math.max(maxSplit, split);
} else {
for (int i = index; i < length; i++) {
String substr = s.substring(index, i + 1);
if (set.add(substr)) {
backtrack(i + 1, split + 1, s, set);
set.remove(substr);
}
}
}
}
}
python3 解法, 执行用时: 240 ms, 内存消耗: 15 MB, 提交时间: 2022-12-09 16:24:03
class Solution:
def maxUniqueSplit(self, s: str) -> int:
def backtrack(index: int, split: int):
if index >= length:
nonlocal maxSplit
maxSplit = max(maxSplit, split)
else:
for i in range(index, length):
substr = s[index:i+1]
if substr not in seen:
seen.add(substr)
backtrack(i + 1, split + 1)
seen.remove(substr)
length = len(s)
seen = set()
maxSplit = 1
backtrack(0, 0)
return maxSplit