LeetCode 3563. Lexicographically Smallest String After Adjacent Removals
weekly contest 451。
雖然是承接 Q2,但是難度跨度也太大了,而且還是複雜度妙妙屋。
題目
https://leetcode.com/problems/lexicographically-smallest-string-after-adjacent-removals/description/
解法
連續定義同 Q2,即在字母表中絕對差為 1 或 25 的兩個字母。
每次操作可從 s 中刪除任意一對相鄰且連續的字母。
求任意次操作後可得的字典序最小結果。
繼續用括號相消為例,將可刪除的連續字母以括號表示。
研究怎樣的模式可以被刪除,最後成為空字串:
- 最單純的相鄰連續,如 ()
- 多個區間互相包含,如 ([])
- 多個括號並排,如 ()[]
若區間 s[i..j] 要能刪除,需要滿足以上任一情況。
不同的刪除順序可能得到剩餘的子區間,有重疊的子問題,考慮 dp。
定義 can_remove(i, j):是否可透過操作刪除 s[i..j]。
若須滿足以下任一情況,則可刪除為空:
- s[i..j] 相鄰且連續。
- s[i+1..j-1] 可被刪除,最後使得 s[i] 和 s[j] 變成相鄰且連續。
- s[i..mid] 可被刪除,另一段 s[mid+1..j] 也可被刪除
知道能不能刪之後,再來決定 s 中的字元要不要刪,是選或不選的問題。
不同的刪法也可能得到相同的結果,有重疊的子問題,還是 dp。
定義 dp(i):s[i..] 若干次刪除後可得的最小字典序字串。
轉移:
- 不刪 s[i],結果為 s[i] + dp(i+1)
- 刪 s[i],需要找長度為 2 個區間 s[i..j] 刪除,結果為 f(j+1)
題目求 s[0..] 若干次刪除得到的最小字典序結果。
答案入口 dp(0)。
時間複雜度 O(N^3)。
空間複雜度 O(N^2)。
def is_consecutive(x, y):
diff = abs(ord(x) - ord(y))
return diff == 1 or diff == 25
class Solution:
def lexicographicallySmallestString(self, s: str) -> str:
N = len(s)
@cache
def can_remove(i, j):
if i+1 == j:
return is_consecutive(s[i], s[j])
if is_consecutive(s[i], s[j]) and can_remove(i+1, j-1):
return True
for mid in range(i+1, j, 2):
if can_remove(i, mid) and can_remove(mid+1, j):
return True
return False
@cache
def dp(i):
if i == N:
return ""
# keep s[i]
res = s[i] + dp(i+1)
# remove s[i..j]
for j in range(i+1, N, 2):
if can_remove(i, j):
res = min(res, dp(j+1))
return res
return dp(0)