删列造序 III

难度: Hard

给定由 n 个小写字母字符串组成的数组 strs ，其中每个字符串长度相等。

选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

比如，有 strs = ["abcdef","uvwxyz"] ，删除索引序列 {0, 2, 3} ，删除后为 ["bef", "vyz"] 。

假设，我们选择了一组删除索引 answer ，那么在执行删除操作之后，最终得到的数组的行中的 每个元素 都是按字典序排列的（即 (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) 和 (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) ，依此类推）。

请返回 answer.length 的最小可能值 。

示例 1：

输入：strs = ["babca","bbazb"]
输出：3
解释：
删除 0、1 和 4 这三列后，最终得到的数组是 strs = ["bc", "az"]。
这两行是分别按字典序排列的（即，strs[0][0] <= strs[0][1] 且 strs[1][0] <= strs[1][1]）。
注意，strs[0] > strs[1] —— 数组 strs 不一定是按字典序排列的。

示例 2：

输入：strs = ["edcba"]
输出：4
解释：如果删除的列少于 4 列，则剩下的行都不会按字典序排列。

示例 3：

输入：strs = ["ghi","def","abc"]
输出：0
解释：所有行都已按字典序排列。

提示：

n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i] 由小写英文字母组成

Submission

运行时间: 75 ms

内存: 16.1 MB

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        if len(strs) == 0:
            return 0
        dp = [1] * len(strs[0])
        for i in range(1, len(strs[0])):
            for j in range(i - 1, -1, -1):
                is_less = True
                for s in strs:
                    if s[j] > s[i]:
                        is_less = False
                        break

                if is_less:
                    dp[i] = max(dp[i], dp[j] + 1, 1)

        return len(strs[0]) - max(dp)

Explain

此题的思路是使用动态规划找出最长的按字典序排列的子序列。我们用一个数组 dp 来记录每个位置作为子序列结束位置时的最大长度。对于每个字符位置 i，我们检查前面所有的位置 j (j < i)，并判断 strs 中的所有字符串是否在 j 到 i 位置的字符是按字典序排列的。如果是，那么我们尝试用 dp[j] + 1 更新 dp[i]。最后，由于我们需要删除的列数是总列数减去最长有序子序列的长度，因此结果为列总数减去 dp 中的最大值。

时间复杂度: O(m^2 * n)

空间复杂度: O(m)

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        if len(strs) == 0:  # 如果输入为空，则不需要删除任何列
            return 0
        dp = [1] * len(strs[0])  # 初始化 dp 数组，每个位置初始为1
        for i in range(1, len(strs[0])):  # 遍历每个字符位置
            for j in range(i - 1, -1, -1):  # 检查所有前面的位置
                is_less = True
                for s in strs:  # 检查每个字符串是否有序
                    if s[j] > s[i]:
                        is_less = False
                        break

                if is_less:  # 如果有序，则尝试更新 dp[i]
                    dp[i] = max(dp[i], dp[j] + 1, 1)

        return len(strs[0]) - max(dp)  # 返回总列数减去最大有序子序列长度

Explore

动态规划数组 dp 的初始化为1是基于这样的考虑：即使在最不利的情况下，每个字符位置本身都可以被视为一个长度为1的有序子序列。因此，每个位置的最小可能的有序子序列长度确实是1，代表该位置字符自身成为一个子序列。这样初始化保证了在动态规划的过程中，每个字符至少能构成一个长度为1的子序列。

如果输入的字符串数组 strs 不为空，但每个字符串的长度为0，意味着没有任何列存在。在这种情况下，由于没有列可供删除，因此所需删除的列数也应为0。这是因为初始问题是基于列的删除来整理顺序，没有列自然也就没有需要删除的列。

在得到 dp 数组的最大值后，直接用字符串的长度减去这个最大值得到答案是基于这样的逻辑：dp 数组的最大值代表在所有字符串中能够形成的最长有序子序列的长度。因此，要使整个数组有序，需要删除的列数即为总列数减去这个最长有序子序列的长度。这种简化是合理的，因为我们的目标是减少删除的列数，同时保持字符串数组中每个字符串的相对顺序。这种方法直接给出了达到这一目标的最少删除次数。