0960-删列造序 III

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

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

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

假设，我们选择了一组删除索引 answer ，那么在执行删除操作之后，最终得到的数组的行中的 每个元素 都是按 字典序 排列的（即
(strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) 和
(strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) ，依此类推）。

请返回 _ answer.length 的最小可能值_ 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i] 由小写英文字母组成

方法 1：动态规划

想法和算法

这是一个复杂的问题，很难抽象出解题思路。

首先，找出需要保留的列数，而不是需要删除的列数。最后，可以相减得到答案。

假设我们一定保存第一列 C，那么保存的下一列 D 就必须保证每行都是字典有序的，也就是 C[i] <= D[i]。那么我们就可以删除 C 和 D 之间的所有列。

我们可以用动态规划来解决这个问题，让 dp[k] 表示在输入为 [row[k:] for row in A] 时保存的列数，那么 dp[k] 的递推式显而易见。

[]class Solution {
    public int minDeletionSize(String[] A) {
        int W = A[0].length();
        int[] dp = new int[W];
        Arrays.fill(dp, 1);
        for (int i = W-2; i >= 0; --i)
            search: for (int j = i+1; j < W; ++j) {
                for (String row: A)
                    if (row.charAt(i) > row.charAt(j))
                        continue search;

                dp[i] = Math.max(dp[i], 1 + dp[j]);
            }

        int kept = 0;
        for (int x: dp)
            kept = Math.max(kept, x);
        return W - kept;
    }
}

[]class Solution(object):
    def minDeletionSize(self, A):
        W = len(A[0])
        dp = [1] * W
        for i in xrange(W-2, -1, -1):
            for j in xrange(i+1, W):
                if all(row[i] <= row[j] for row in A):
                    dp[i] = max(dp[i], 1 + dp[j])

        return W - max(dp)

复杂度分析

时间复杂度：O(N * W^2)，其中 N 是 A 的长度，W 是 A 中每个单词的长度。
空间复杂度：O(W)。