本文主要是介绍leetcode 1239. 串联字符串的最大长度——回溯+位运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1239. 串联字符串的最大长度
题目
给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
示例
输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
解析
我们需要计算可行解的长度，至于可行解具体是什么，以及可行解中各个字符的顺序我们是不用考虑的。因此构成可行解的每个字符串均可以视作一个字符集合，且集合不含重复元素。所以我么可以用二进制01代表对应的小写字母是否存在，所以我们就可以用位运算进行求解。
首先将arr数组中自身包含有重复的元素就可以直接删除掉，将自身不包含重复的转换为二进制数后存在一个list集合中。
最后用回溯的方法来求解最长的不包含的重复字符的子字符串的长度。
backtrace（list集合，pos表示遍历到list集合的哪一个位置了，mask表示标记可以存入字符串连接后的二进制数）
回溯结束的条件就是pos的值等于了list集合的长度，更新最长的长度，就结束了。
当遍历都pos时候有两种情况，选或者不选，当和mask没有重复的元素的时候选择，有重复的就不选。然后直接遍历下一个pos，mask不变。注意：这里不是if和else的关系。因为就算是有重复，选了之后，也要进行从下一个位置开始，否则就都是从第一个位置开始算起来的。
代码Java
class Solution {int count;public int maxLength(List<String> arr) {//回溯、加位运算List<Integer> masks=new ArrayList<Integer>();for(String str:arr){int mask=0;for(int i=0;i<str.length();++i){//开始判断str里面是否存在相同的字符，存在的话就舍弃，不存在的话转化为二进制的书，存进list集合里面int ch=str.charAt(i)-'a';if(((mask>>ch)&1)!=0){ //存在的话就breakmask=0;break;}mask=mask|(1<<ch); //将ch加进去到mask中去}if(mask!=0){masks.add(mask);}}//加入完毕后，就可以回溯进行判断，不断的更新最长的值backtrace(masks,0,0); //第二个参数指的是遍历到mask的位置，第三个参数指的是return count;}void backtrace(List<Integer> masks, int pos, int mask) {//返回的条件if(masks.size()==pos){count=Math.max(count,Integer.bitCount(mask));return;}//如果可以加入的话if((mask&masks.get(pos))==0){backtrace(masks,pos+1,mask|masks.get(pos));}backtrace(masks,pos+1,mask);}
}
这篇关于leetcode 1239. 串联字符串的最大长度——回溯+位运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
