[LeetCode] 960. Delete Columns to Make Sorted III

[grandyang]

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = ["babca","bbazb"] and deletion indices {0, 1, 4}, then the final array after deletions is ["bc","az"].

Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.

For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]), and so on.

Return the minimum possible value of D.length.

Example 1:

Input: ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn't necessarily in lexicographic order.

Example 2:

Input: ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row won't be lexicographically sorted.

Example 3:

Input: ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.

Note:

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

这道题说是给了一个字符串数组A，其中每个字符串的长度均相同，现在需要删除一些特定位置上的字符，需要使得留下的字符是按照字母顺序排列的，问最少需要删除多少列。这道题需要借助题目中给的例子来理解，因为每个字符串长度相同，若每行放一个字符串，那么其实也可以看作是一个二维的字符数组，要删除最少的列，使得每行都是有序的。实际上最差的情况就是每行都是倒序的，就要移除 n-1 列，只留下一列，若每行只有一个字符，则一定是符合题意。最好的情况就是给定每行已经都是有序的，则一列都不用移除，所以最终的结果是在一定的范围之内的，即 [0, n-1]，其中n是字符串的长度。假如只有一个字符串，为了使其有序，需要移除最小的列数，移除之后剩下的就是有序的。那么其实就是等同于找出该字符串中的最大递增序列的长度，即之前那道 Longest Increasing Subsequence 的做法，然后用总长度减去这个 LIS 长度，即为最少移除的列数。若有多行的情况，这个 LIS 必须是所有行都满足的，才符合题意。这里维护一个一维 dp 数组，其中 dp[i] 表示以 A[][i] 为结尾的最长递增子串的长度，对于每一个 A[][i]，从该行第一个数再搜索到i，此时由于有多行，每一行都要判断一下，假如出现 A[][j] 大于 A[][i] 的情况，说明当前列不能组成 LIS，直接 break。只有每行都符合要求，并且 dp[j]+1 大于 d[i] 时，将 dp[i] 赋值为 dp[j]+1。当每次 dp[i] 更新了之后，用 n-dp[i] 来更新结果 res 即可，参见代码如下：

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int m = A.size(), n = A[0].size(), res = n - 1, k = 0;
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                for (k = 0; k < m; ++k) {
                    if (A[k][j] > A[k][i]) break;
                }
                if (k == m && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
            res = min(res, n - dp[i]);
        }
        return res;
    }
};

讨论：可能会有同学有疑问，会出现 dp[j]+1 小于 dp[i] 的情况么，其实是有的，比如 "cbbdabc"，i = 6，是最后一个c，因为前面有前面出现了 bb，所以此时的 dp[6] = 3，当 j = 4 时，是中间的a，前面没有比a小的字母，所以 dp[4] = 1，此时就出现了 dp[j]+1 小于 dp[i] 的情况。

Github 同步地址:

#960

类似题目：

Longest Increasing Subsequence

Delete Columns to Make Sorted

Delete Columns to Make Sorted II

参考资料：

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/discuss/206861/C%2B%2B-7-lines-DP-O(n-*-n-*-m)

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/discuss/205679/C%2B%2BJavaPython-Maximum-Increasing-Subsequence

LeetCode All in One 题目讲解汇总(持续更新中...)