Problem
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 a stringĀ "
abcdef
"
Ā and deletion indicesĀ {0, 2, 3}
, then the final string after deletionĀ isĀ "
bef
"
.
Suppose we chose a set of deletion indicesĀ D
Ā such that after deletions, each remaining column in A is inĀ non-decreasingĀ sorted order.
Formally, theĀ c
-th column isĀ [A[0][c], A[1][c], ..., A[A.length-1][c]]
Return the minimum possible value ofĀ D.length
.
Example 1:
Input: ["cba","daf","ghi"] Output: 1
Example 2:
Input: ["a","b"] Output: 0
Example 3:
Input: ["zyx","wvu","tsr"] Output: 3
Note:
1 <= A.length <= 100
1 <= A[i].length <= 1000
Solution: Simulation
Check descending case column by column.
Time complexity: O(NL)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua, 64 ms class Solution { public: int minDeletionSize(vector<string>& A) { int ans = 0; for (int c = 0; c < A[0].size(); ++c) for (int r = 1; r < A.size(); ++r) { if (A[r][c] < A[r - 1][c]) { ++ans; break; } } return ans; } }; |