0960. Delete Columns to Make Sorted III

题目信息

题号:

0960

难度:

Hard

主题:

字符串数组、统一删列、行内非递减

原题:

LeetCode 0960

重点:

从所有字符串中删除相同列后,要求每一行自身按字符非递减;行与行之间不需要保持字典序,目标是最小删除列数

题目重述

给定由等长小写字符串组成的数组 strs。可以选择若干列下标,并从每个字符串中同时删除这些位置的字符,剩余字符保持原相对顺序。

删除后,对于每一个字符串 row,都必须满足 row[0] <= row[1] <= ...。不同字符串之间不作大小比较。请返回达到该条件需要删除的最少列数。

1 <= strs.length <= 100,1 <= strs[i].length <= 100,所有字符串长度相同。

自建示例

保留首尾两列即可让每行有序:

输入:strs = ["bab","cac"]
输出:1
解释:删除第 1 列后得到 "bb" 和 "cc",每一行都非递减;原字符串在 b 到 a、c 到 a 处下降,因此不能不删除。

每一行原本都非递减:

输入:strs = ["ab","bc"]
输出:0
解释:两行中的字符都已从左到右非递减,不需要删除任何列。