関小君刷题记

题目大意：

给你一个字符串 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 仅包含小写英文字母

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1593

解题思路分析：

这是一道典型的动态规划题目，由于我们无法一眼看出哪种切割方式最优，那么没关系，我们一种一种去尝试即可。对于DP类题目，我习惯使用递归方式解题，本题也不例外。

首先我们建立一个递归函数help(),参数中传入一个index代表当前的起始下标，另外再传入一个List集合，用于排重。因此该递归函数的意义是，从当前index到字符串结尾，合理拆分子串的最大数目。

递归中，我们尝试从当前下标开始选取一段子串进行切割，切割的位置可以是当前位置到字符串末尾的任意一位，由于我们无法得知哪一种切割最优，因此我们循环尝试每一种切割，对于当前切割的子串[index, i]，首先查看List集合中是否存在，如果存在，说明该切割不合理，循环到下一个切割点。反之，当前切割成立，我们将子串加入到List集合中，同时，将剩下的部分（起始下标位置i+1）交给子问题去处理。递归结束的条件为当前起始下标越界。此时List集合中元素的个数即是子串切割数量，用该数量更新全局最大值即可。

实现代码：

int max=0; // 最大切割数量
public int maxUniqueSplit(String s) {
    help(s.toCharArray(),0,new ArrayList<>()); // 递归求解
    return max;
}

void help(char[] arr, int index, List<String> temp){
    if(index==arr.length){ // 如果下标越界
        // 利用当前数组内元素个数，更新全局最大值
        if(temp.size()>max) max=temp.size();
        return;
    }
    // 当前切割子串
    StringBuilder sb=new StringBuilder();
    for(int i=index;i<arr.length;i++){ // 循环每个切割点
        sb.append(arr[i]); // 将当前字符加入切割子串中
        if(temp.contains(sb.toString())) continue; // 如果存在该子串，跳过
        temp.add(sb.toString()); // 将该子串加入集合
        help(arr, i+1, temp); // 将剩余部分递归至子问题
        temp.remove(sb.toString()); // 移除当前子串，并尝试下一种分割
    }
}

本题解法执行时间为82ms。

Runtime: 82 ms, faster than 33.33% of Java online submissions for Split a String Into the Max Number of Unique Substrings.

Memory Usage: 39.5 MB, less than 66.67% of Java online submissions for Split a String Into the Max Number of Unique Substrings.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1593-split-a-string-into-the-max-number-of-unique-substrings-解题思路分析/