一、题目

给定一个字符串数组 arr，字符串 s是将 arr 某一子序列字符串连接所得的字符串，如果 s中的每一个字符都只出现过一次，那么它就是一个可行解。

请返回所有可行解 s中最长长度。

点击查看原题
难度级别：中等

二、思路

1）二进制表示+回溯法

根据题意，要求可行解中字符都只出现过一次，如果每次都对每个字符进行计数，那重复子问题太大，最好的办法就是用一个方法去记录，可以使用二进制的方法记录，由于只有小写字母，每个字符对应一个位，用change数组记录。（如果单个字符串有重复字符，则change[i]=0）
由于只要每个字符出现过一次，和顺序无关。（这个很关键）
使用回溯法，每个串就只有两种选择，加入或不加入，用一个val记录当前已经加入的字符串，val的二进制中为1的位对应不同字符。

(val & change[loc]) == 0，则loc位置的字符串与当前拼接的字符串不冲突，可以加进来

三、代码

1）二进制表示+回溯法

  1. class Solution {
  2.     private int ans = 0;
  3.     public int maxLength(List<String> arr) {
  4.         int[] change = new int[arr.size()];
  5.         for (int i = 0; i < arr.size(); i++) {
  6.             for (char c : arr.get(i).toCharArray()) {
  7.                 if ((change[i] & (1 << (c - 'a'))) != 0) {    // 查询是否该字符是否出现过
  8.                     change[i] = 0;
  9.                     break;
  10.                 }
  11.                 change[i] = change[i] | (1 << (c - 'a'));
  12.             }
  13.         }
  14.         backTrace(change, 0, 0);
  15.         return ans;
  16.     }
  17.     private void backTrace(int[] change, int loc, int val) {
  18.         if (change.length == loc) {
  19.             ans = Math.max(ans, Integer.bitCount(val));    
  20.             return ;
  21.         }
  22.         if (change[loc] != 0 && (val & change[loc]) == 0) {    
  23.             // 只有loc位置的字符串无重复字符，且与当前拼接的字符串拼接在一起无重复字符才可以进行迭代
  24.             backTrace(change, loc + 1, val | change[loc]);
  25.         }
  26.         backTrace(change, loc + 1, val);    // 不拼接loc位置字符串的情况
  27.     }
  28. }

len为所有字符串长度之和，n为arr长度，时间复杂度为O(len+2^n)，空间复杂度为O(n)