1593. 拆分字符串使唯一子字符串的数目最大 #
- 标签:哈希表、字符串、回溯
- 难度:中等
题目大意 #
给定一个字符串 s
。将字符串 s
拆分后可以得到若干非空子字符串,这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是唯一的 。
要求:拆分该字符串,并返回拆分后唯一子字符串的最大数目。
注意:子字符串是字符串中的一个连续字符序列。
解题思路 #
维护一个全局变量 ans
用于记录拆分后唯一子字符串的最大数目。并使用集合 s_set
记录不重复的子串。
-
从下标为
0
开头的子串回溯。 -
对于下标为
index
开头的子串,我们可以在index + 1
开始到len(s) - 1
的位置上,分别进行子串拆分,将子串拆分为s[index: i + 1]
。 -
如果当前子串不在
s_set
中,则将其存入s_set
中,然后记录当前拆分子串个数,并从i + 1
的位置进行下一层递归拆分。然后在拆分完,对子串进行回退操作。 -
如果拆到字符串
s
的末尾,则记录并更新ans
。 -
在开始位置还可以进行以下剪枝:如果剩余字符个数 + 当前子串个数 <= 当前拆分后子字符串的最大数目,则直接返回。
最后输出 ans
。
代码 #
|
|