LeetCode刷题之路 删列造序 II

删列造序 II【中等】

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

选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。

比方，有 A = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 A 为["bef", "vyz"]。

假设，我们选择了一组删除索引 D，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（A[0] <= A[1] <= A[2] ... <= A[A.length - 1]）排列的，而后请你返回 D.length 的最小可能值。

示例 1：

输入：["ca","bb","ac"]输出：1解释： 删除第一列后，A = ["a", "b", "c"]。现在 A 中元素是按字典排列的 (即，A[0] <= A[1] <= A[2])。我们至少需要进行 1 次删除，由于最初 A 不是按字典序排列的，所以答案是 1。

示例 2：

输入：["xc","yb","za"]输出：0解释：A 的列已经是按字典序排列了，所以我们不需要删除任何东西。注意 A 的行不需要按字典序排列。也就是说，A[0][0] <= A[0][1] <= ... 不肯定成立。

示例 3：

输入：["zyx","wvu","tsr"]输出：3解释：我们必需删掉每一列。

提醒：

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 100

解题思路

作者有点笨，做了好久这道题还是没通过，于是就参考了大佬们的解答，下面就大佬的代码说一下这道题的解题思路吧。首先思考什么样的序列才是字典序，所谓字典序就是像查字典一样。如果我们想查hui这个音，先要找到y字母的那部分，而后会看见很多以y开头的拼音，就要进行挑选找出yu，进而找出yui。在这里一样，字典序就是像['xy','yy','za']，['xa','xc','yb']这类的。于是做这道题就要思考以下几种情况：

1.看能否有序，假如无序，直接删除。

例：[    'xcz',    'zdv',    'yfa'    ]    上面第一列分别是x、z、y,并不是有序的，于是放弃这一列进行下一列的判断。

2.假如有序，看能否有相等元素，假如没有，直接返回结果。

例：[    'xcz',    'zdv',    'yfa'    ]    第一列按照情况1解决，直接删除。而后判断第二列，第二列有序并且不含相等元素，所以直接返回结果为1。

3.假如有相等元素，得到相等元素的下标，而后对后面的列只判断有相等元素的几行。

例：[    'xcz',    'zcv',    'yfa'    ]    如果第二列变成了c、c、f，含有相等元素，就需要进行第三列的判断，    对第三列的判断也是按照情况1、2、3依次判断的，直到满足条件返回结果。

按照上面的情况分析之后，思路就已经很清楚了，就是取出所有列，依次对情况1,2,3进行判断，最后返回相应的结果值。下面是leetcode上的代码：

class Solution:    def minDeletionSize(self, A):        """        :type A: List[str]        :rtype: int        """        def isright(i,l):#第i列能否按照严格字典序（不含相等），这里只比较l中出现的行数            for j in l:                if A[j][i] > A[j+1][i]:                    return 1            return 0        def isequal(i,l):#第i列能否有的情况，这里只比较l中出现的行数，有的话返回1和相等的行标号            flag = 0            child = []            for j in l:                if A[j][i] == A[j+1][i]:                    child.append(j)                    flag = 1            return flag,child        res = 0;        child = range(len(A)-1)        for i in range(len(A[0])):            h = isright(i,child)            if h == 0:                eq,child1 = isequal(i,child)                if eq == 0:                    return res                elif eq == 1:                    child = child1            res += h        return res