[LeetCode] 955. Delete Columns to Make Sorted II

[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 = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef","vyz"].

Suppose we chose a set of deletion indices D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] ... <= A[A.length - 1]).

Return the minimum possible value of D.length.

Example 1:

Input: ["ca","bb","ac"]
Output: 1
Explanation:
After deleting the first column, A = ["a", "b", "c"].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.

Example 2:

Input: ["xc","yb","za"]
Output: 0
Explanation:
A is already in lexicographic order, so we don't need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= ...)

Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3
Explanation:
We have to delete every column.

Note:

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

这道题说是给了一个字符串数组，里面的字符串长度均相同，这样如果将每个字符串看作一个字符数组的话，于是就可以看作的一个二维数组，题目要求数组中的字符串是按照字母顺序的，问最少需要删掉多少列。可以看到跟之前那道题 Delete Columns to Make Sorted 的不同之处，那道题是要求每列上的字符都是非递减顺序的，而这道题要求的是字符串是按字母顺序的。我们知道比较两个长度相等的字符串的字母顺序时，就是从开头起按照两两对应的位置比较，只要前面的字符顺序已经比出来了，后面的字符的顺序就不用管了，比如 "bx" 和 "ea"，因为 b 比 e 小，所以 "bx" 比 "ea" 小，后面的 x 和 a 的顺序无关紧要。如果看成二维数组的话，在比较 A[i][j] 和 A[i+1][j] 时，假如 [0, j-1] 中的某个位置k，已经满足了 A[i][k] < A[i+1][k] 的话，这里就不用再比了，所以用一个数组 sorted 来标记某相邻的两个字符串之间是否已经按照字母顺序排列了。然后用两个 for 循环，外层是遍历列，内层是遍历行，然后看若 sorted[i] 为 false，且 A[i][j] > A[i + 1][j] 的话，说明当前列需要被删除，结果 res 自增1，且 break 掉内层 for 循环。当内层 for 循环 break 掉或者自己结束后，此时看 i 是否小于 m-1，是的话说明是 break 掉的，直接 continue 外层循环。若是自己退出的，则在遍历一遍所有行，更新一下 sorted 数组即可，参见代码如下：

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

Github 同步地址:

#955

类似题目：

Delete Columns to Make Sorted

参考资料：

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

https://leetcode.com/problems/delete-columns-to-make-sorted-ii/discuss/203171/C%2B%2B-12-ms-brute-force

https://leetcode.com/problems/delete-columns-to-make-sorted-ii/discuss/203182/JavaC%2B%2BPython-Greedy-Solution-O(MN)

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