1239.串联字符串的最大长度

链接：1239.串联字符串的最大长度
难度：Medium
标签：位运算、数组、字符串、回溯
简介：给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。请返回所有可行解 s 中最长长度。

题解 1 - typescript

• 编辑时间：2021-06-19
• 执行用时：188ms
• 内存消耗：43.8MB
• 编程语言：typescript
• 解法介绍：利用二进制储存，进行比较。

function maxLength(arr: string[]): number {
  const masks = arr
    .map(s => {
      if (s === '') return -1;
      let mask = 0;
      for (const c of s) {
        const num = c.codePointAt(0)!;
        if ((mask >> num) & 1) return -1;
        mask |= 1 << num;
      }
      return mask;
    })
    .filter(num => num !== -1);
  let ans = 0;
  const masksLen = masks.length;
  const dfs = (index = 0, num = 0) => {
    if (index === masksLen) {
      ans = Math.max(ans, num.toString(2).split('0').join('').length);
      return;
    }
    if ((num & masks[index]) === 0) dfs(index + 1, num | masks[index]);
    dfs(index + 1, num);
  };
  dfs();
  return ans;
}