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.
- Runtime: 8 ms, faster than 100.00% of C++ online submissions for Delete Columns to Make Sorted II.
- Memory Usage: 819.2 KB, Less than 48.15% of C++ online submissions for Delete Columns to Make Sorted II.
- class Solution {
- public:
- int minDeletionSize(vector<string>& A) {
- int ret = 0;
- bool sorted[A.size()];
- for(int i=0; i<A.size(); i++) sorted[i] = false;
- for(int i=0; i<A[0].size(); i++) {
- int j = 0;
- for(; j<A.size()-1; j++) {
- if(!sorted[j] && (A[j][i]> A[j+1][i])) {
- ret++;
- break;
- }
- }
- if(j < A.size()-1) continue;
- j = 0;
- for(; j<A.size()-1; j++) {
- if(A[j][i] < A[j+1][i]) sorted[j] = true;
- }
- }
- return ret;
- }
- };
来源: http://www.bubuko.com/infodetail-2944921.html