0955. Delete Columns to Make Sorted II¶
题目信息¶
- 题号:
0955
- 难度:
Medium
- 主题:
字符串数组、统一删列、字典序
- 原题:
- 重点:
对所有字符串删除相同下标集合后,要求字符串数组按原行顺序呈非递减字典序;目标是最小删除列数
题目重述¶
给定由等长小写字符串组成的数组 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",不需要删除任何列。