関小君刷题记

题目大意：

串联字符串的最大长度

给定一个字符串数组 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.

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