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