※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: 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.有点像0/1背包问题 每一轮都去决定 arr[i] 拿与不拿 然后新增可能性
在挑 arr[i] 要不要拿的时候必须先知道 arr[i-1] 之前的结果
这个结果应该要能代表之前挑的字 concate 出来的字串
写抽象点就是如果 dp[i-1][字串s] == True 并且字串s和 arr[i] 没有重复字符
那就能更新 dp[i][字串s+arr[i]] == True
最后去找 dp[-1][s] == True 中最大的一个
2. 这里就可以用一个常见的手法 bitmasking 去当 index
也就是用 1 << k 去代表 'a' + k 这个字符有没有出现过
例如 ...0000101 = 'ac'
...0011010 = 'bde'
这样就可以用 0~2^26 去表示目前取的字串有出现哪些字母
dp[i][j] 的范围就是 size(arr) * (2^26)
3. 因为 dp[i][j] == False 的情况下没办法更新 dp[i+1] 中的其他人
所以对 dp[i] 我们只要知道目前是 True 的那些 j 就好
一样有个常见的手法 就是对 dp[i] 开一个 dict 去记 key = j, value = dp[i][j]
这样就可以不用 iterate 到那些 False 的点
4. 最后也是考虑到 dp[i-1] 只会影响到 dp[i]
等于只要维护一个 dict 每轮更新他就好 省了一点空间
class Solution:
def maxLength(self, arr: List[str]) -> int:
dp, nextdp = {0:0}, {}
def mask(s):
res = 0
for c in s:
if res & 1 << (ord(c) - ord('a')):
return -1
res |= 1 << (ord(c) - ord('a'))
return res
for word in arr:
m = mask(word)
if m == -1:
continue
for key in dp:
if m & key == 0:
nextdp[m|key] = dp[key] + len(word)
nextdp[key] = dp[key]
dp, nextdp = nextdp, {}
return max(dp.values())
5.其实也不用每轮都换一个新的 dict 直接 append 进去就好
mask 也可以省掉直接用 set(a) & set(b) 判断 a, b 两个 string 有没有重复
lee215 的 code:
def maxLength(self, A):
dp = [set()]
for a in A:
if len(set(a)) < len(a): continue
a = set(a)
for c in dp[:]:
if a & c: continue
dp.append(a | c)
return max(len(a) for a in dp)
果然还是要靠 lee