📌 📄 内容摘要:
@ninijia 在 Leetcode每日一题练习 ------ 1593. 拆分字符串使唯一子字符串的数目最大 中发帖
从Leetcode 每日一题练习继续讨论：
1593. 拆分字符串使唯一子字符串的数目最大
1593. Split a String Into the Max Number of Unique Substrings
题解
本题最初会想到可以使用贪心+哈希表的方式解题。考虑题目要求最多能分割成多少个不一样的子字符串，则每次分割分割出一个尽可能短的字符串，在总长固定的情况下，就能得到尽可能多的字符串。但本题中局部最优并不一定是全局最优，这是因为我们分割时的遍历是从前向后遍历的，而能分割出数量最多的字符串可能将比较短的字符串放在中间位置才能得到。即分割出的比较短的字符串不一定总在整个字符串的前面。因此贪心不是总能得到最优解。
则可以考虑遍历所有的分割组合找到分割个数最多的组合。可以使用递归结合回溯的方式遍历所有的分割组合。递归函数中分割时从当前的起始位置开始，依次分割长度为1，2…的字符...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/237734/1
─────────────────────────────
📢 来源：LINUX DO
