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 <= 161 <= arr[i].length <= 26arr[i]中只含有小写英文字母
思路
- 读题
题目需要的字符串是一个没有重复字符的字符串, 所提供的字符串数组, 可以进行拼接, 得到最长的那个没有重复字符的字符串.
回溯法(递归)+DFS剪枝
分析算法规模: 递归深度最多16层, 运算规模最大2^17(回溯树上节点)
遍历所有可能的解, 尝试不同字符串的组合(回溯)
代码实现
回溯法(递归)+DFS剪枝
class Solution {
private int ans = 0;
public int maxLength(List<String> arr) {
if (arr == null) {
return 0;
}
// 遍历整个字符串数组 获得符合条件的单个字符串最大长度
for (String ar : arr) {
if (nonDuplicate(ar)) {
ans = Math.max(ar.length(), ans);
}
}
// DFS 从0开始 初始字符串为空串
helper(arr, 0, "");
return ans;
}
private void helper(List<String> arr, int idx, String prev) {
// 剪枝 没有重复(符合条件)才可以继续往下走
if (nonDuplicate(prev)) {
ans = Math.max(prev.length(), ans);
} else {
return;
}
// 最后一个节点 返回
if (idx > arr.size()) {
return;
}
// 当前字符串
String cur = arr.get(idx);
// 添加
helper(arr, idx + 1, prev + cur);
// 不添加
helper(arr, idx + 1, prev);
}
private boolean nonDuplicate(String str) {
return str.chars().distinct().count() == str.length();
}
}