LeetCode 2901. Longest Unequal Adjacent Groups Subsequence II
雙周賽115。最近好幾次都是題目內容完全一樣,只改測資範圍就當成兩題,所以有人都做第二題然後去前面貼一樣的code。
結果這次好了,內容有差異,答案邏輯還完全不一樣,騙到不少人。
題目
輸入整數n,以及字串陣列words[i]還有整數陣列groups,兩者長度皆為n。
漢明距離指的是兩個等長等長字串中,對應字元不同的位置數。
你必須從索引陣列[0, 1, …, n - 1]中選擇一個最長子序列,記為[i0, i1, …, ik - 1],子序列長度記為k。
對於所有介於0 < j + 1 < k的j,必須滿足:
- groups[ij] != groups[ij+1]
- words[ij]和[ij+1]等長,且漢明距離為1
回傳一個陣列字串,依序由該子序列中的索引對應words中的字串而成。若有多個答案,則回傳任意一個。
注意:words中的字串長度可能不同。
解法
題目真的超長超囉嗦,但其實就是變化版的LIS。
只是銜接條件不是元素遞增,而是不同組+漢明距離1。
先寫一個函數ok(i,j)來判斷兩索引能不能銜接。
定義dp(i):由words[i]結尾的最長子序列。
轉移方程式:max(dp(j) FOR ALL 0<=j<i) + words[i]
base case:dp(i)只有一個選擇,就是words[i]。
注意:dp保存的是字串子序列本身,而不是長度。更新最大值要取子序列長度。
時間複雜度O(n^2)。
空間複雜度O(n^2)。
class Solution:
def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
def ok(i,j):
if groups[i]==groups[j]:
return False
if len(words[i])!=len(words[j]):
return False
return sum(c1!=c2 for c1,c2 in zip(words[i],words[j]))==1
@cache
def dp(i):
longest=[]
for j in range(i):
if ok(i,j):
t=dp(j)
if len(t)>len(longest):
longest=t
return longest+[words[i]]
ans=[]
for i in range(n):
t=dp(i)
if len(t)>len(ans):
ans=t
return ans
也可以把len當成max函數的判斷方式,這樣就可以直接傳入子序列本身。
class Solution:
def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
def ok(i,j):
if groups[i]==groups[j]:
return False
if len(words[i])!=len(words[j]):
return False
return sum(c1!=c2 for c1,c2 in zip(words[i],words[j]))==1
@cache
def dp(i):
longest=[]
for j in range(i):
if ok(i,j):
longest=max(longest,dp(j),key=len)
return longest+[words[i]]
return max([dp(i) for i in range(n)],key=len)
在計算dp(i)的過程中,會試著從數個索引j轉移過來。
如果額外維護一個陣列fa,其中fa[i]代表i的轉移來源,那麼就可以只保存子序列長度,最後從利用fa逆向建構出整個子序列。
時間複雜度O(N^2)。
空間複雜度O(N)。
class Solution:
def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
def ok(i,j):
if groups[i]==groups[j]:
return False
if len(words[i])!=len(words[j]):
return False
return sum(c1!=c2 for c1,c2 in zip(words[i],words[j]))==1
fa=[-1]*n
@cache
def dp(i):
res=0
for j in range(i):
if ok(i,j):
t=dp(j)
if t>res:
res=t
fa[i]=j
return res+1
mx=0
mxi=None
for i in range(n):
t=dp(i)
if t>mx:
mx=t
mxi=i
ans=[None]*mx
curr=mxi
for i in reversed(range(mx)):
ans[i]=words[curr]
curr=fa[curr]
return ans