What is the primary strategy for solving the "Delete Columns to Make Sorted II" problem?

The primary strategy is to use a greedy approach with invariant validation, ensuring the lexicographic order is maintained by deleting columns when necessary.

How do we decide which columns to delete in the "Delete Columns to Make Sorted II" problem?

We delete columns if their characters disrupt the lexicographic order across rows. This ensures minimal deletions while maintaining the desired order.

Can this problem be solved with dynamic programming?

While dynamic programming is not the optimal solution for this problem, it could be adapted. The greedy approach combined with invariant validation is more efficient.

What is the time complexity of the "Delete Columns to Make Sorted II" problem?

The time complexity is O(n * m), where n is the number of strings and m is the length of each string, as we check each column and compare rows.

What is the best way to handle edge cases in "Delete Columns to Make Sorted II"?

Edge cases like already sorted arrays or arrays with no required deletions should be handled early in the algorithm to avoid unnecessary computations.

#955

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

删列造序 II

给定由 n 个字符串组成的数组 strs ，其中每个字符串长度相等。选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。比如，有 strs = ["abcdef", "uvwxyz"] ，删除索引序列 {0, 2, 3} ，删除后 strs 为 ["bef", "vy…

数组字符串贪心

题目描述

给定由 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] 由小写英文字母组成

lightbulb

解题思路

方法一：贪心

字符串按字典序比较时，从左到右比较，第一个不相等的字符决定了两个字符串的大小关系。因此我们可以从左到右遍历每一列，判断当前列是否需要删除。

我们维护一个长度为 $n - 1$ 的布尔数组 $\textit{st}$ ，表示相邻的字符串对是否已经确定了大小关系。如果已经确定了大小关系，那么后续在这两个字符串之间的任何字符比较都不会改变它们的大小关系。

对于每一列 $j$ ，我们遍历所有相邻的字符串对 $(\textit{strs}[i], \textit{strs}[i + 1])$ ：

如果 $\textit{st}[i]$ 为假且 $\textit{strs}[i][j] > \textit{strs}[i + 1][j]$ ，说明当前列必须删除，我们将答案加一并跳过该列的处理；
否则，如果 $\textit{st}[i]$ 为假且 $\textit{strs}[i][j] < \textit{strs}[i + 1][j]$ ，说明当前列确定了这两个字符串的大小关系，我们将 $\textit{st}[i]$ 设为真。

遍历完所有列后，答案即为需要删除的列数。

这个贪心策略是最优的，因为字典序由从左到右第一个不同列决定。若当前列不删除且导致某对字符串顺序错误，则无论后续列如何，都无法修正这一错误，因此必须删除当前列。若当前列不删除且不导致任何字符串对顺序错误，则保留当前列不会影响最终的字典序关系。

时间复杂度 $O(n \times m)$ ，空间复杂度 $O(n)$ ，其中 $n$ 和 $m$ 分别为字符串数组的长度和每个字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        m = len(strs[0])
        st = [False] * (n - 1)
        ans = 0
        for j in range(m):
            must_del = False
            for i in range(n - 1):
                if not st[i] and strs[i][j] > strs[i + 1][j]:
                    must_del = True
                    break
            if must_del:
                ans += 1
            else:
                for i in range(n - 1):
                    if not st[i] and strs[i][j] < strs[i + 1][j]:
                        st[i] = True
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the approach to checking each column and comparing rows, typically O(n * m), where n is the number of strings and m is the length of each string. Space complexity is usually O(1), but may vary based on the approach used to track deleted columns.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates a clear understanding of greedy algorithms and invariant validation.
question_mark
Candidate is able to identify when and why column deletions are necessary based on lexicographic order.
question_mark
Candidate can efficiently walk through each column and validate the condition without unnecessary recomputations.

warning

常见陷阱

外企场景

error
Forgetting to check lexicographic order after each column deletion, leading to unnecessary deletions.
error
Confusing this problem with problems that require sorting entire rows, rather than focusing on column deletions.
error
Not considering edge cases like an already sorted array or cases where no deletions are needed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a variant where the strings are of varying lengths but still require lexicographic ordering.
arrow_right_alt
A version where deletions can be performed at the row level instead of the column level, altering the complexity.
arrow_right_alt
A variation where you are given a set of allowed deletions and need to minimize them to maintain the order.

help

常见问题

外企场景

继续练习

#942 增减字符串匹配 #1578 使绳子变成彩色的最短时间 #179 最大数