Welcome to Subscribe On Youtube
960. Delete Columns to Make Sorted III
Description
You are given an array of n
strings strs
, all of the same length.
We may choose any deletion indices, and we delete all the characters in those indices for each string.
For example, if we have strs = ["abcdef","uvwxyz"]
and deletion indices {0, 2, 3}
, then the final array after deletions is ["bef", "vyz"]
.
Suppose we chose a set of deletion indices answer
such that after deletions, the final array has every string (row) in lexicographic order. (i.e., (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1])
, and (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1])
, and so on). Return the minimum possible value of answer.length
.
Example 1:
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.
Example 2:
Input: strs = ["edcba"] Output: 4 Explanation: If we delete less than 4 columns, the only row will not be lexicographically sorted.
Example 3:
Input: strs = ["ghi","def","abc"] Output: 0 Explanation: All rows are already lexicographically sorted.
Constraints:
n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i]
consists of lowercase English letters.
Solutions
-
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; } };
-
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)
-
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 }
-
function minDeletionSize(strs: string[]): number { const n = strs[0].length; const f: number[] = Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { let ok = true; for (const s of strs) { if (s[j] > s[i]) { ok = false; break; } } if (ok) { f[i] = Math.max(f[i], f[j] + 1); } } } return n - Math.max(...f); }
-
impl Solution { pub fn min_deletion_size(strs: Vec<String>) -> i32 { let n = strs[0].len(); let mut f = vec![1; n]; for i in 1..n { for j in 0..i { if strs.iter().all(|s| s.as_bytes()[j] <= s.as_bytes()[i]) { f[i] = f[i].max(f[j] + 1); } } } (n - *f.iter().max().unwrap()) as i32 } }