本文共 1372 字，大约阅读时间需要 4 分钟。

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
   
     arr) {        //回溯、加位运算        List
    
      masks=new ArrayList
     
      ();        for(String str:arr){            int mask=0;            for(int i=0;i
      
       >ch)&1)!=0){           //存在的话就break                    mask=0;                    break;                }                mask=mask|(1<
       
         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);    }}
       
      
     
    
   

转载地址：http://gtgji.baihongyu.com/