LEETCODE 1593. Split a String Into the Max Number of Unique Substrings 解题思路分析

题目大意:

给你一个字符串 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.

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

发表评论

电子邮件地址不会被公开。