LEETCODE 1239. Maximum Length of a Concatenated String with Unique Characters解题思路分析

题目大意:

串联字符串的最大长度

给定一个字符串数组 arr,字符串 s 是将 arr 某一子序列字符串连接所得的字符串,如果 s 中的每一个字符都只出现过一次,那么它就是一个可行解。

请返回所有可行解 s 中最长长度。

示例 1:

输入:arr = ["un","iq","ue"]
输出:4
解释:所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique",最大长度为 4。

示例 2:

输入:arr = ["cha","r","act","ers"]
输出:6
解释:可能的解答有 "chaers" 和 "acters"。

示例 3:

输入:arr = ["abcdefghijklmnopqrstuvwxyz"]
输出:26

提示:

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[i] 中只含有小写英文字母

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

解题思路分析:

本题可以归结到递归问题,按顺序遍历每一个单词,对于当前字符串,如果与之前组好的字符串没有相同字符,那么我们可以选择将其串联或者不串联,如果当前字符串与之前组好的字符串存在相同字符,那么我们无法将其串联。标准的递归思路。看下实现代码:

public int maxLength(List<String> arr) {
    // 递归寻找最优解
    return helper(arr, 0, "");
}
// arr为字符串列表
// index为当前字符串
// temp为之前串联好的字符串
// 返回结果为最长串联字符串长度
int helper(List<String> arr, int index, String temp){
    // 如果index越界,返回之前串联好字符串的长度
    if(index==arr.size()) return temp.length();
    int max=0; // 返回结果
    // 查看当前字符串与之前串联好的字符串是否存在相同字符
    boolean isUnique = isUnique(new String[]{arr.get(index), temp});
    if(isUnique){ // 不存在相同字符
        // 将当前字符串进行串联,递归到下一个字符串
        max = helper(arr, index+1, temp+arr.get(index));
        // 不串联当前字符串,递归到下一个字符串
        max = Math.max(max, helper(arr, index+1, temp));
    }else{ // 存在相同字符
        // 别无选择,只能不串联当前字符串,递归到下一个字符串
        max = helper(arr, index+1, temp);
    }
    return max;
}
// 查看两个字符串是否不含有相同字符
boolean isUnique(String[] strs){
    int[] count = new int[26];
    for(String str : strs){
        for(int i=0;i<str.length();i++){
            if(count[str.charAt(i)-'a']++==1) return false;
        }
    }
    return true;
}

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

Runtime: 10 ms, faster than 71.83% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.

Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Maximum Length of a Concatenated String with Unique Characters.

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

发表评论

您的电子邮箱地址不会被公开。