960. Delete Columns to Make Sorted III

LeetCode hard оригинал: C# #array #csharp #dynamic-programming #graph #hard #leetcode #math #search #sort #string

LeetCode Static

Вам дан массив из n строк 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.

Пример:

Input: strs = ["babca","bbazb"]

Output: 3

Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].

Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).

Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

C# решение

сопоставлено/оригинал

public class Solution {
    public int MinDeletionSize(string[] A) {
        int W = A[0].Length;
        int[] dp = new int[W];
        Array.Fill(dp, 1);
        for (int i = W - 2; i >= 0; --i) {
            for (int j = i + 1; j < W; ++j) {
                bool valid = true;
                foreach (string row in A) {
                    if (row[i] > row[j]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[i] = Math.Max(dp[i], 1 + dp[j]);
                }
            }
        }
        return W - dp.Max();
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinDeletionSize(vector<string> A) {
        int W = A[0].size();
        vector<int>& dp = new int[W];
        Array.Fill(dp, 1);
        for (int i = W - 2; i >= 0; --i) {
            for (int j = i + 1; j < W; ++j) {
                bool valid = true;
                foreach (string row in A) {
                    if (row[i] > row[j]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[i] = max(dp[i], 1 + dp[j]);
                }
            }
        }
        return W - dp.Max();
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public int minDeletionSize(String[] A) {
        int W = A[0].length();
        int[] dp = new int[W];
        Arrays.fill(dp, 1);
        for (int i = W-2; i >= 0; --i)
            search: for (int j = i+1; j < W; ++j) {
                for (String row: A)
                    if (row.charAt(i) > row.charAt(j))
                        continue search;

                dp[i] = Math.max(dp[i], 1 + dp[j]);
            }

        int kept = 0;
        for (int x: dp)
            kept = Math.max(kept, x);
        return W - kept;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        W = len(A[0])
        dp = [1] * W

        for i in range(W - 2, -1, -1):
            for j in range(i + 1, W):
                if all(row[i] <= row[j] for row in A):
                    dp[i] = max(dp[i], 1 + dp[j])

        return W - max(dp)

Go решение

сопоставлено/оригинал

func minDeletionSize(A []string) int {
    W := len(A[0])
    dp := make([]int, W)
    for i := range dp {
        dp[i] = 1
    }

    for i := W - 2; i >= 0; i-- {
        for j := i + 1; j < W; j++ {
            valid := true
            for _, row := range A {
                if row[i] > row[j] {
                    valid = false
                    break
                }
            }
            if valid {
                dp[i] = max(dp[i], 1 + dp[j])
            }
        }
    }

    kept := 0
    for _, x := range dp {
        kept = max(kept, x)
    }

    return W - kept
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Вместо поиска количества удаляемых столбцов, найдем количество столбцов, которые нужно сохранить. В конце мы можем вычесть это значение, чтобы получить желаемый ответ.

Используйте динамическое программирование, чтобы решить проблему. Пусть dp[k] будет количеством столбцов, которые сохраняются, начиная с позиции k. Мы будем искать максимальное значение dp[k], чтобы найти количество столбцов, которые нужно сохранить.

Итоговое количество удаляемых столбцов будет равно общей длине строк минус количество сохраненных столбцов.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.