What is the time complexity of the 'Delete Columns to Make Sorted' 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 need to iterate through each column.

How do you handle edge cases in the 'Delete Columns to Make Sorted' problem?

Edge cases like single-row grids or already sorted columns are handled by checking if any deletions are needed at all, returning 0 if no deletions are required.

How does the array plus string pattern apply to this problem?

The problem combines both array manipulation and string comparison to identify columns that are not lexicographically sorted, requiring an array-based solution for efficient column checking.

Can dynamic programming be used to solve 'Delete Columns to Make Sorted'?

While dynamic programming could be applied, the most straightforward solution is a linear scan through columns, making dynamic programming unnecessary for this problem.

What would happen if the grid contains a mix of uppercase and lowercase letters?

The problem's solution assumes lowercase English letters, but if uppercase letters are introduced, you would need to handle case-sensitive comparisons appropriately.

#944

Easy

auto_awesome数组·string

LeetCode 题解工作台

删列造序

给你由 n 个小写字母字符串组成的数组 strs ，其中每个字符串长度相等。这些字符串可以每个一行，排成一个网格。例如， strs = ["abc", "bce", "cae"] 可以排列为： abc bce cae 你需要找出并删除不是按字典序非严格递增排列的列。在上面的例子（下标从 0 开…

数组字符串

题目描述

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

这些字符串可以每个一行，排成一个网格。例如，strs = ["abc", "bce", "cae"] 可以排列为：

abc
bce
cae

你需要找出并删除 不是按字典序非严格递增排列的 列。在上面的例子（下标从 0 开始）中，列 0（'a', 'b', 'c'）和列 2（'c', 'e', 'e'）都是按字典序非严格递增排列的，而列 1（'b', 'c', 'a'）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：

输入：strs = ["cba","daf","ghi"]
输出：1
解释：网格示意如下：
  cba
  daf
  ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。

示例 2：

输入：strs = ["a","b"]
输出：0
解释：网格示意如下：
  a
  b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：网格示意如下：
  zyx
  wvu
  tsr
所有 3 列都是非升序排列的，所以都要删除。

提示：

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

lightbulb

解题思路

方法一：逐列比较

我们记字符串数组 $\textit{strs}$ 的行数为 $n$ ，列数为 $m$ 。

遍历每一列，从第二行开始，逐列比较当前行和上一行的字符，如果当前行的字符小于上一行的字符，说明当前列不是按字典序非严格递增排列的，需要删除，结果加一，然后跳出内层循环。

最后返回结果即可。

时间复杂度 $O(L)$ ，其中 $L$ 为字符串数组 $\textit{strs}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate how to check each column independently for sorting.
question_mark
Watch for handling edge cases like one-column grids or already sorted grids.
question_mark
A strong candidate will optimize the solution efficiently, keeping the complexity in mind.

warning

常见陷阱

外企场景

error
Not handling edge cases like grids with a single string or already sorted columns.
error
Misunderstanding the requirement of comparing columns rather than rows.
error
Overcomplicating the solution or using excessive space when only a few variables are needed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the grid contains a mix of uppercase and lowercase characters? Ensure you handle character comparison correctly.
arrow_right_alt
Can the problem be solved using dynamic programming? Consider whether a DP-based solution would improve efficiency.
arrow_right_alt
What if the grid size increases significantly? Would this approach scale well with large inputs?

help

常见问题

外企场景

继续练习

#943 最短超级串 #942 增减字符串匹配 #949 给定数字能组成的最大时间