#955
Delete Columns to Make Sorted II
specialist · 885 · lc medium +31 · verified · 49.7% accepted · 1,041 likes · top 37%
Description
Given n equal-length strings strs laid out in a grid, remove the fewest columns so that the remaining sequence of strings is in lexicographically non-decreasing order from top to bottom. Return the number of columns removed.
Example 1:
Input: strs = ["ca","bb","ac"]
Output: 1
Explanation:
After deleting the first column, strs = ["a", "b", "c"].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.
Example 2:
Input: strs = ["xc","yb","za"]
Output: 0
Explanation:
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)
Example 3:
Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: We have to delete every column.
Code
1
2
3