Medium
题目描述
给定由 n 个字符串组成的数组 strs，所有字符串都具有相同的长度。
我们可以选择任意删除索引，并删除每个字符串中这些索引处的字符。
例如，如果我们有 strs = [“abcdef”,“uvwxyz”] 和删除索引 {0, 2, 3}，那么删除后的最终数组是 [“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] 由小写英文字母组成
解题思路
这道题的核心思想是贪心策略：我们逐列检查，如果当前列能够保持或增强字典序，就保留它；否则就删除。
关键洞察：
- 已确定顺序的字符串对：一旦某两个字符串在前面的列中已经确定了字典序关系（如 str[i] < str[i+1]），那么后续列对这两个字符串的顺序就不再重要了
- 未确定顺序的字符串对：只有那些在前面所有保留列中都相等的字符串对，才需要继续考虑它们在当前列的大小关系
算法流程：
- 维护一个
sorted数组，标记哪些相邻字符串对已经确定了字典序关系 - 对每一列，先检查是否会破坏已有的字典序：对于未确定顺序的相邻字符串对，如果当前列使得前面的字符大于后面的字符，则必须删除当前列
- 如果当前列不会破坏字典序，则保留它，并更新
sorted数组：对于那些在当前列中前面字符小于后面字符的未确定字符串对，将其标记为已确定
这是一个典型的贪心问题，每次都做局部最优选择（能保留就保留），最终得到全局最优解。
推荐解法：贪心算法，时间复杂度最优。
代码实现
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int n = strs.size();
int m = strs[0].size();
vector<bool> sorted(n - 1, false);
int deletions = 0;
for (int j = 0; j < m; j++) {
bool needDelete = false;
// 检查当前列是否破坏字典序
for (int i = 0; i < n - 1; i++) {
if (!sorted[i] && strs[i][j] > strs[i + 1][j]) {
needDelete = true;
break;
}
}
if (needDelete) {
deletions++;
} else {
// 更新已确定顺序的字符串对
for (int i = 0; i < n - 1; i++) {
if (!sorted[i] && strs[i][j] < strs[i + 1][j]) {
sorted[i] = true;
}
}
}
}
return deletions;
}
};
class Solution:
def minDeletionSize(self, strs: List[str]) -> int:
n = len(strs)
m = len(strs[0])
sorted_pairs = [False] * (n - 1)
deletions = 0
for j in range(m):
need_delete = False
# 检查当前列是否破坏字典序
for i in range(n - 1):
if not sorted_pairs[i] and strs[i][j] > strs[i + 1][j]:
need_delete = True
break
if need_delete:
deletions += 1
else:
# 更新已确定顺序的字符串对
for i in range(n - 1):
if not sorted_pairs[i] and strs[i][j] < strs[i + 1][j]:
sorted_pairs[i] = True
return deletions
public class Solution {
public int MinDeletionSize(string[] strs) {
int n = strs.Length;
int m = strs[0].Length;
bool[] sorted = new bool[n - 1];
int deletions = 0;
for (int j = 0; j < m; j++) {
bool needDelete = false;
// 检查当前列是否破坏字典序
for (int i = 0; i < n - 1; i++) {
if (!sorted[i] && strs[i][j] > strs[i + 1][j]) {
needDelete = true;
break;
}
}
if (needDelete) {
deletions++;
} else {
// 更新已确定顺序的字符串对
for (int i = 0; i < n - 1; i++) {
if (!sorted[i] && strs[i][j] < strs[i + 1][j]) {
sorted[i] = true;
}
}
}
}
return deletions;
}
}
var minDeletionSize = function(strs) {
const n = strs.length;
const m = strs[0].length;
const sorted = new Array(n - 1).fill(false);
let deletions = 0;
for (let j = 0; j < m; j++) {
let needDelete = false;
// 检查当前列是否破坏字典序
for (let i = 0; i < n - 1; i++) {
if (!sorted[i] && strs[i][j] > strs[i + 1][j]) {
needDelete = true;
break;
}
}
if (needDelete) {
deletions++;
} else {
// 更新已确定顺序的字符串对
for (let i = 0; i < n - 1; i++) {
if (!sorted[i] && strs[i][j] < strs[i + 1][j]) {
sorted[i] = true;
}
}
}
}
return deletions;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n × m) | n 为字符串个数，m 为字符串长度，需要遍历每一列 |
| 空间复杂度 | O(n) | 需要 sorted 数组记录相邻字符串对的状态 |