题目描述

给定由 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 的最小可能值。

样例

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

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

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

注意

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

算法

(枚举) $\Theta(nm)$

1. 相同长度序列字典序的比较方式：两个序列从头开始比较，如果中途出现了不一样的字符，则以该字符为大小为字典序的大小。
2. 此时定义一个数组 end，表示当前序列是否还应该与后继序列作比较。初始时都是应该的。
3. 然后从第一列开始枚举，如果按照 end 数组，当前列不符合单调不降，则删除该列且答案加一；否则，直接更新 end 数组，如果某个序列不再和后继序列作比较（即当前列的字符不同），则 end[i] 更新为 false 即可。

时间复杂度

• 共枚举 $m$ 列，每次都需要 $O(n)$ 的时间判定，$\Theta(n)$ 的时间更新 end 数组，故总时间复杂度为 $\Theta(nm)$。

C++ 代码

class Solution {
public:

    int minDeletionSize(vector<string>& A) {
        int n = A.size(), m = A[0].length();
        int ans = 0;
        bool flag;
        vector<bool> end(n, false);

        for (int i = 0; i < m; i++) {

            flag = true;
            for (int j = 0; j < n - 1; j++)
                if (!end[j]) {
                    if (A[j][i] > A[j + 1][i]) {
                        flag = false;
                        break;
                    }
                }

            if (!flag) {
                ans++;
            }
            else {
                for (int j = 0; j < n - 1; j++)
                    if (A[j][i] < A[j + 1][i]) {
                        end[j] = true;
                    }
            }
        }

        return ans;
    }
};