推 qwer338859: 難怪標籤有Bit Manipulation 10/24 17:24
推 NTHUlagka: 大師 10/24 19:52
※ 引述《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
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.195.223 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1666603150.A.2E0.html