1239. Maximum Length of a Concatenated String with Unique Characters
给予一个字串阵列arr，判断里面的任意字串拼接后的最长字串长度，需满足：
1.任意字串拼接时不可改变相对于arr的先后顺序，例如：arr = {"a", "b"} 的话
不可以这样拼："ba"，其中不拼接任何字串拿到的字串例如："a" "b" 也是合法的。
2.拼接完的字串必须每个字符都是独特的：
"a" (O) 长度为1
"aa" (X) 非法，长度为0
Example：
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" +
"ers") and "acters" ("act" + "ers").
思路：
1.我研究了一下应该是只能穷举，因为要穷举所以就用回溯法来剪枝。
2.每次都从start加入当前字串到列表并进入下层。
3.当curr的size > 1 时，检查是否包含重复字符，若包含重复字符直接返回0，后面都
不用找了，否则计算共有几个字符并令他为max。
4.比较当前max和往更深处找的数字哪个大更新并max，最后返回max。
JavaCode：
class Solution {
public int maxLength(List<String> arr) {
return backTracking(arr, new ArrayList<>(), 0);
}
private int backTracking(List<String> arr, List<String> curr, int start) {
if(start > arr.size()) return 0;
int max = 0;
int[] count = new int[26];
for(String s: curr) {
for(char c : s.toCharArray()){
if(count[c - 'a'] != 0)
return 0;
count[c - 'a']++;
max++;
}
}
for(int i = start; i < arr.size(); i++) {
curr.add(arr.get(i));
max = Math.max(max, backTracking(arr, curr, i + 1));
curr.remove(curr.size() - 1);
}
return max;
}
}
芒果假面
https://i.imgur.com/acHi4CL.png