• Leetcode 3563. Lexicographically Smallest String After Adjacent Removals
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3563. Lexicographically Smallest String After Adjacent Removals

1. 解題思路

這次的最后一題同樣沒有自力搞定，簡直了……

這道題還是一個動態規劃的題目，就是提前構建一下消解空間，給定一個$N^2$的矩陣dp，其中任意元素dp[i][j]表示子串s[i:j+1]是否可以被可以被完全remove掉。

然后，我們就只需要考察一下從尾部到頭部每一個元素被消除以及不被消除的兩種情況下所能獲得的最優解即可。

2. 代碼實現

給出python代碼實現如下：

class Solution:def lexicographicallySmallestString(self, s: str) -> str:n = len(s)remEmpty = [[False] * n for _ in range(n)]def is_consecutive(a, b):d = abs(ord(a) - ord(b))return d == 1 or d == 25for i in range(n - 1):if is_consecutive(s[i], s[i + 1]):remEmpty[i][i + 1] = Truefor L in range(4, n + 1, 2):for i in range(n - L + 1):j = i + L - 1for k in range(i + 1, j + 1, 2):if is_consecutive(s[i], s[k]) and (k == i + 1 or remEmpty[i + 1][k - 1]) and (k == j or remEmpty[k + 1][j]):remEmpty[i][j] = Truebreakf = [""] * (n + 1)for i in range(n - 1, -1, -1):best = s[i] + f[i + 1]for j in range(i + 1, n, 2):if remEmpty[i][j] and f[j + 1] < best:best = f[j + 1]f[i] = bestreturn f[0]

提交代碼評測得到：耗時6771ms，占用內存18.5MB。