删列造序 II

难度: Medium

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

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

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

假设，我们选择了一组删除索引 answer，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]）排列的，然后请你返回 answer.length 的最小可能值。

示例 1：

输入：strs = ["ca","bb","ac"]
输出：1
解释： 
删除第一列后，strs = ["a", "b", "c"]。
现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。
我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。

示例 2：

输入：strs = ["xc","yb","za"]
输出：0
解释：
strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。
注意 strs 的行不需要按字典序排列。
也就是说，strs[0][0] <= strs[0][1] <= ... 不一定成立。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：
我们必须删掉每一列。

提示：

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

Submission

运行时间: 35 ms

内存: 16.0 MB

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        m, n, ans = len(strs), len(strs[0]), 0
        seps = set()
        for j in range(n):
            f = set()
            for i in range(m - 1):
                if i not in seps:
                    if strs[i][j] > strs[i + 1][j]:
                        ans += 1
                        break
                    if strs[i][j] < strs[i + 1][j]:
                        f.add(i)
            else:
                seps |= f
        return ans

Explain

该题解的思路是：遍历字符串数组每一列，判断当前列是否需要删除。具体做法是，用一个集合 seps 记录当前已经满足字典序的行索引。遍历每一列时，先初始化一个空集合 f，用于记录新增的满足字典序的行索引。然后遍历相邻两行，如果上一行的字符大于下一行，说明不满足字典序，直接将答案加1，并退出当前列的判断；如果上一行的字符小于下一行，则将上一行的索引加入 f 集合。如果内层遍历结束，说明当前列满足字典序，将 f 集合并入 seps。最后返回答案。

时间复杂度: O(mn)

空间复杂度: O(m)

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        m, n, ans = len(strs), len(strs[0]), 0
        seps = set()  # 记录已经满足字典序的行索引
        for j in range(n):  # 遍历每一列
            f = set()  # 记录新增的满足字典序的行索引
            for i in range(m - 1):  # 遍历相邻两行
                if i not in seps:  # 如果当前行还不满足字典序
                    if strs[i][j] > strs[i + 1][j]:  # 如果上一行字符大于下一行
                        ans += 1  # 答案加1
                        break  # 退出当前列的判断
                    if strs[i][j] < strs[i + 1][j]:  # 如果上一行字符小于下一行
                        f.add(i)  # 将上一行索引加入f集合
            else:  # 如果内层循环顺利结束，说明当前列满足字典序
                seps |= f  # 将f集合并入seps
        return ans

Explore

集合seps用于记录在之前的列检查中，已经确定满足字典序的行索引。这意味着对于在seps中的行索引，我们不需要再次确认它们在后续列的字典序关系。而集合f是用来记录在当前列检查过程中新确认满足字典序的行索引。它们帮助算法优化性能，避免重复检查已经满足条件的行，从而减少不必要的比较操作。使用这两个集合可以有效地跟踪和更新哪些行之间的顺序关系已经被字典序确定，这样在处理每一列时只关注未确定的行索引，提高效率。

这种处理方式不会导致忽略后续行可能满足字典序的情况。因为如果在某一列中存在上一行的字符大于下一行的字符，这已经足以证明整列不满足字典序要求，无论后续行的字符如何。因此，直接增加删除计数并停止当前列的进一步检查是有效且必要的，确保算法的效率和简洁性。

当上一行字符小于下一行字符时，加入集合f是因为这确定了这两行在当前列的字典序关系。当字符相等时，当前列无法确定这两行的顺序关系，因此不将其加入f集合。这种情况下，我们需要在后续的列继续观察这两行来决定其字典序关系。这种处理保证了只有明确满足字典序的行索引被记录，而不确定的关系则留待后续列进行判断。

在此算法中选择使用集合主要是因为集合提供了高效的成员检查和添加操作，特别是对于不重复元素的管理。集合能够快速地进行元素的查找、添加和合并操作，这些操作的平均时间复杂度通常是O(1)，这对于算法中频繁的检查和更新操作是非常有利的。与列表相比，集合避免了重复元素的问题并提供更快的查找速度；与字典相比，集合的操作更简单直接，因为这里只需要跟踪元素的存在性，而不需要存储额外的键值对信息。