难度：★★★☆☆
类型：数组
方法：贪心算法

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

解答

我们从前往后遍历各列，每次遇到可以使得整体保持升序的列，则将该列添加到结果中，否则，需要删除该列。

这里需要注意的是，对于["ac", "bb", "ca"]之类的数组，虽然第二列不是按照顺序排列的，但是由于第一列的存在，第二列是否有序已经不重要了，也可以添加到数组中。因此，判断一列是否有序，前提是目前的字符串数组中是否存在上一个字母一样的情况，如果存在才需要判断。

代码中的r是字符串数组，其中的单词永远有序。

class Solution:
    def minDeletionSize(self, strs) -> int:
        num_s, num_c = len(strs), len(strs[0])
        r = ['' for _ in range(num_s)]
        ans = 0
        for i in range(num_c):
            for j in range(num_s-1):
                if r[j] == r[j + 1] and strs[j][i] > strs[j + 1][i]:
                    ans += 1
                    break
            else:
                for j in range(num_s):   # 保留该列
                    r[j] += strs[j][i]
        return ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析