Hard

题目描述

给你一个由 n 个相同长度的字符串组成的数组 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] 由小写英文字母组成

解题思路

这是一个动态规划问题。我们需要找到最长的保留列序列，使得每一行在保留这些列后都保持字典序。

思路分析：

  1. 核心思想：转换问题，从"最少删除多少列"变为"最多能保留多少列"，最终答案就是总列数减去保留列数。

  2. 状态定义：定义 dp[i] 表示以第 i 列结尾的最长保留序列长度。

  3. 状态转移：对于每一列 i，检查是否能接在之前的某一列 j 后面。条件是：

    • 对于所有行，第 j 列的字符都小于等于第 i 列的字符
    • 如果满足条件，则 dp[i] = max(dp[i], dp[j] + 1)

  4. 验证函数：需要一个辅助函数来判断列 j 是否可以在列 i 之前，即检查是否对所有行都有 strs[row][j] <= strs[row][i]。

  5. 边界情况：每一列本身都可以作为长度为 1 的序列，所以 dp[i] = 1。

时间复杂度：O(m²n)，其中 m 是列数，n 是行数。对于每对列都要检查所有行。

推荐解法：动态规划，这是最直观且效率较高的解法。

代码实现

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size();
        int m = strs[0].length();
        
        vector<int> dp(m, 1);
        
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                bool canKeep = true;
                for (int k = 0; k < n; k++) {
                    if (strs[k][j] > strs[k][i]) {
                        canKeep = false;
                        break;
                    }
                }
                if (canKeep) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int maxKeep = *max_element(dp.begin(), dp.end());
        return m - maxKeep;
    }
};

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        m = len(strs[0])
        
        dp = [1] * m
        
        for i in range(1, m):
            for j in range(i):
                can_keep = True
                for k in range(n):
                    if strs[k][j] > strs[k][i]:
                        can_keep = False
                        break
                if can_keep:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        max_keep = max(dp)
        return m - max_keep

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int n = strs.Length;
        int m = strs[0].Length;
        
        int[] dp = new int[m];
        for (int i = 0; i < m; i++) {
            dp[i] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                bool canKeep = true;
                for (int k = 0; k < n; k++) {
                    if (strs[k][j] > strs[k][i]) {
                        canKeep = false;
                        break;
                    }
                }
                if (canKeep) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int maxKeep = dp.Max();
        return m - maxKeep;
    }
}

var minDeletionSize = function(strs) {
    const n = strs.length;
    const m = strs[0].length;
    
    const dp = new Array(m).fill(1);
    
    for (let i = 1; i < m; i++) {
        for (let j = 0; j < i; j++) {
            let canKeep = true;
            for (let k = 0; k < n; k++) {
                if (strs[k][j] > strs[k][i]) {
                    canKeep = false;
                    break;
                }
            }
            if (canKeep) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    const maxKeep = Math.max(...dp);
    return m - maxKeep;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m²n)
空间复杂度O(m)

其中 m 是字符串长度（列数），n 是字符串数量（行数）。