题目

难度：★★☆☆☆
类型：字符串

给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。

选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。 所余下的字符串行从上往下读形成列。

比如，有 A = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 A 为["bef", "vyz"]， A 的列分别为["b","v"], ["e","y"], ["f","z"]。（形式上，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。

假设，我们选择了一组删除索引 D，那么在执行删除操作之后，A 中所剩余的每一列都必须是 非降序 排列的，然后请你返回 D.length 的最小可能值。

提示
1 <= A.length <= 100
1 <= A[i].length <= 1000

示例

示例 1
输入：["cba", "daf", "ghi"]
输出：1
解释：
当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。
若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。

示例 2
输入：["a", "b"]
输出：0
解释：D = {}

示例 3
输入：["zyx", "wvu", "tsr"]
输出：3
解释：D = {0, 1, 2}

解答

这道题虽然题目看起来庞大，但是想表达的道理很简单：

以例子1为例，有这样一个表：

单词	第一列	第二列	第三列
单词1	c	b	a
单词2	d	a	f
单词3	g	h	i

要删除表中一些列，这里删除了第二列，获得表：

单词	第一列	第三列
单词1	c	a
单词2	d	f
单词3	g	i

这样每一列都是非降序了。

可以观察到，要删除不是非降序的列即可实现任务，通过统计表中不是非降序的列的总数即可。

因此我们可以逐列比较，比较当前列排序前后是否一致，统计所有不一致的情况，即为所求。

class Solution:
    def minDeletionSize(self, A):
        """
        :type A: List[str]
        :rtype: int
        """
        res = 0
        for i in zip(*A):
            if list(i) != sorted(i):
                res += 1
        return res

紧凑写法：

class Solution:
    def minDeletionSize(self, A):
        """
        :type A: List[str]
        :rtype: int
        """
        return sum([list(c) != sorted(c) for c in zip(*A)])

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