代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定由 n
个小写字母字符串组成的数组 strs
,其中每个字符串长度相等。
选取一个删除索引序列,对于 strs
中的每个字符串,删除对应每个索引处的字符。
比如,有 strs = ["abcdef","uvwxyz"]
,删除索引序列 {0, 2, 3}
,删除后为 ["bef", "vyz"]
。
假设,我们选择了一组删除索引 answer
,那么在执行删除操作之后,最终得到的数组的行中的 每个元素 都是按字典序排列的(即 (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1])
和 (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1])
,依此类推)。
请返回 answer.length
的最小可能值 。
示例 1:
输入:strs = ["babca","bbazb"] 输出:3 解释: 删除 0、1 和 4 这三列后,最终得到的数组是 strs = ["bc", "az"]。 这两行是分别按字典序排列的(即,strs[0][0] <= strs[0][1] 且 strs[1][0] <= strs[1][1])。 注意,strs[0] > strs[1] —— 数组 strs 不一定是按字典序排列的。
示例 2:
输入:strs = ["edcba"] 输出:4 解释:如果删除的列少于 4 列,则剩下的行都不会按字典序排列。
示例 3:
输入:strs = ["ghi","def","abc"] 输出:0 解释:所有行都已按字典序排列。
提示:
n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i]
由小写英文字母组成class Solution:
def minDeletionSize(self, strs: List[str]) -> int:
n = len(strs[0])
dp = [1] * n
for i in range(1, n):
for j in range(i):
if all(s[j] <= s[i] for s in strs):
dp[i] = max(dp[i], dp[j] + 1)
return n - max(dp)
class Solution {
public int minDeletionSize(String[] strs) {
int n = strs[0].length();
int[] dp = new int[n];
Arrays.fill(dp, 1);
int mx = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (check(i, j, strs)) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
mx = Math.max(mx, dp[i]);
}
return n - mx;
}
private boolean check(int i, int j, String[] strs) {
for (String s : strs) {
if (s.charAt(i) < s.charAt(j)) {
return false;
}
}
return true;
}
}
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int n = strs[0].size();
vector<int> dp(n, 1);
int mx = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (check(i, j, strs)) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
mx = max(mx, dp[i]);
}
return n - mx;
}
bool check(int i, int j, vector<string>& strs) {
for (string& s : strs)
if (s[i] < s[j])
return false;
return true;
}
};
func minDeletionSize(strs []string) int {
n := len(strs[0])
dp := make([]int, n)
mx := 1
dp[0] = 1
check := func(i, j int) bool {
for _, s := range strs {
if s[i] < s[j] {
return false
}
}
return true
}
for i := 1; i < n; i++ {
dp[i] = 1
for j := 0; j < i; j++ {
if check(i, j) {
dp[i] = max(dp[i], dp[j]+1)
}
}
mx = max(mx, dp[i])
}
return n - mx
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。