0955. Delete Columns to Make Sorted II

题目信息

题号:

0955

难度:

Medium

主题:

字符串数组、统一删列、字典序

原题:

LeetCode 0955

重点:

对所有字符串删除相同下标集合后,要求字符串数组按原行顺序呈非递减字典序;目标是最小删除列数

题目重述

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

删除后必须满足 strs[0] <= strs[1] <= ... 的字典序关系。请返回达到该条件所需删除的最少列数。这里比较的是各行形成的完整字符串,而不是要求每一列单独有序。

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

自建示例

必须删除全部两列:

输入:strs = ["db","ca","aa"]
输出:2
解释:保留任意一列时得到的单字符序列分别为 d、c、a 或 b、a、a,都不是非递减字典序;删除两列后所有字符串都为空并相等。

原数组已经按字典序排列:

输入:strs = ["ax","by","cz"]
输出:0
解释:三个字符串本来就满足 "ax" < "by" < "cz",不需要删除任何列。