leetcode 955

问题

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:

1
2
3
4
5
6
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:

1
2
3
4
5
6
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:

1
2
3
4
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

分析

从第一列开始依次扫描每个字符串的每一列。如果该列是严格递增的状态则说明到目前为止所有的字符串已经完成了字典顺序的匹配。如果有当前行的字符小于后一行的字符的情况，则说明这一列一定要删除。于是就要重点分析第三种情况，就是存在当前行的字符等于后一行字符的情况，这个情况之下我们就需要考虑这两行字符后面列的情况。我们可是使用vector<bool> sorted(n-1) 来表示每一行已经排序的情况。如果有 sorted[i] == true，则说明在之前扫描的行中已经有第 $i$ 行小于第 $i+1$ 的情况，所以现在就不需要在后续的列中再判定这两行的大小关系了。但是需要注意的是，如果该列已经被制定删除，那么由该列所更新的大小关系将无效。因此，首先判断该列是否要被删除，然后再使用该列对行之间的大小关系进行更新。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int m = A.size();
        int n = A[0].size();
        vector<bool> sorted(m-1, false);
        int ans, i, j;
        for (j = 0; j < n; ++j) {
            for (i = 0; i < m-1; ++i) {
                if (!sorted[i] && A[i][j] > A[i+1][j]) {
                    ans++;
                    break;
                }
            }
            if (i < m-1) continue;
            for (int i = 0; i < m-1; ++i) {
                sorted[i] = sorted[i] | (A[i][j] < A[i+1][j]);
            }
        }
        return ans;
    }
};