LeetCode 955

Posted on

Delete COlumns to Make Sorted II

贪心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.

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.

直接从第一行开始，一行一行的向后检查就行，如果每行都是A[i][j]<A[i+1][j] ，那么后面的几列，第i i+1行肯定是满足要求的，不用判断。特殊的情况在于：

1
2
3
4
5
a  b  z
a  c  y
b  x  a
b  x  b
z  a  a

对于前面几列已经递增的行，当前列的大小关系并不重要，只需要关注前面列是相等的情况。这里用了一个数组来表示前面是否已经是递增关系。

1
sort[i]|=A[i].charAt(j)<A[i+1].charAt(j);