What is the core approach for solving the Delete Columns to Make Sorted III problem?

The core approach involves dynamic programming with a state transition technique, where each state tracks the minimum deletions needed to maintain lexicographical order.

How do you optimize the number of deletions for the problem?

The optimization is achieved by applying a dynamic programming approach that evaluates the fewest deletions necessary for sorting the strings in lexicographical order.

Can dynamic programming be used for other array-based problems?

Yes, dynamic programming is widely used in array-based problems, especially for optimization tasks that require decision-making based on prior states, like sorting or pathfinding.

What is the expected time complexity for Delete Columns to Make Sorted III?

The time complexity is O(N * W^2), where N is the number of strings and W is the length of each string.

What role does lexicographical order play in this problem?

Lexicographical order ensures that after performing column deletions, the remaining strings maintain the sorted order. This condition is central to the dynamic programming approach.

#960

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

删列造序 III

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

数组字符串动态规划

题目描述

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示以第 $i$ 列结尾的最长不下降子序列的长度，初始时 $f[i] = 1$ ，答案即为 $n - \max(f)$ 。

考虑计算 $f[i]$ ，我们可以枚举 $j < i$ ，如果对于所有的字符串 $s$ ，有 $s[j] \le s[i]$ ，那么 $f[i] = \max(f[i], f[j] + 1)$ 。

最后，我们返回 $n - \max(f)$ 。

时间复杂度 $O(n^2 \times m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 $\textit{strs}$ 每个字符串的长度和数组的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs[0])
        f = [1] * n
        for i in range(n):
            for j in range(i):
                if all(s[j] <= s[i] for s in strs):
                    f[i] = max(f[i], f[j] + 1)
        return n - max(f)

speed

复杂度分析

指标	值
时间	O(N * W^2)
空间	O(W)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of dynamic programming by breaking down the problem into subproblems.
question_mark
The candidate applies state transition logic in the context of lexicographical order for string arrays.
question_mark
The candidate shows the ability to optimize deletions by evaluating column states.

warning

常见陷阱

外企场景

error
Overcomplicating the deletion strategy by considering unnecessary combinations of deletions.
error
Neglecting to consider lexicographical order while transitioning between states in dynamic programming.
error
Failing to properly implement the dynamic programming table, resulting in incorrect deletions or missing steps.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem to allow deletions based on other constraints, such as length or character range.
arrow_right_alt
Extend the problem to consider lexicographical sorting within different subsets of strings.
arrow_right_alt
Explore the possibility of finding a generalized solution for sorting arrays of arbitrary objects under different sorting rules.

help

常见问题

外企场景

继续练习

#943 最短超级串 #902 最大为 N 的数字组合 #1048 最长字符串链