题目描述

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

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

比如，有 A = ["babca","bbazb"]，删除索引序列 {0, 1, 4}，删除后 A 为 ["bc","az"]。

假设，我们选择了一组删除索引 D，那么在执行删除操作之后，最终得到的数组的行中的每个元素都是按字典序排列的。

清楚起见，A[0] 是按字典序排列的（即，A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]），A[1] 是按字典序排列的（即，A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]），依此类推。

请你返回 D.length 的最小可能值。

样例

输入：["babca","bbazb"]
输出：3
解释：
删除 0、1 和 4 这三列后，最终得到的数组是 A = ["bc", "az"]。
这两行是分别按字典序排列的（即，A[0][0] <= A[0][1] 且 A[1][0] <= A[1][1]）。
注意，A[0] > A[1] —— 数组 A 不一定是按字典序排列的。

输入：["edcba"]
输出：4
解释：如果删除的列少于 4 列，则剩下的行都不会按字典序排列。

输入：["ghi","def","abc"]
输出：0
解释：所有行都已按字典序排列。

注意

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

算法

(动态规划) $O(m^2n)$

1. 状态 $f(i)$ 表示以第 $i$ 列作为结束时，满足条件的最少删除次数。
2. 假设列的下标从 1 开始到 $m$，且每个字符串的第 0 列都是空白。初始值 $f(0) = 0$，其余为正无穷。
3. 转移时，枚举上一次保留的列 $j$，判断第 $j$ 列到第 $i$ 列是否满足条件，若满足则 $f(i) = \min (f(i), f(j) + i - j - 1)$。
4. 最终答案为 $\min (f(i) + m - i)$，其中 $0 \le i \le m$。

时间复杂度

• 状态数为 $m$ 个，每次转移需要枚举 $O(m)$ 个状态，且需要 $O(n)$ 的时间检验合法性，故总时间复杂度为 $O(m^2n)$。

C++ 代码

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int n = A.size(), m = A[0].size();
        vector<int> f(m + 1, m);

        for (int i = 0; i < n; i++)
            A[i] = " " + A[i];

        int ans = m;
        f[0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = i - 1; j >= 0; j--) {
                bool flag = true;
                for (int k = 0; k < n; k++)
                    if (A[k][j] > A[k][i]) {
                        flag = false;
                        break;
                    }

                if (flag) {
                    f[i] = min(f[i], f[j] + i - j - 1);
                }
            }
            ans = min(ans, f[i] + m - i);
        }
        return ans;
    }
};