Sponsored
Sponsored
This approach involves iterating over each column in the grid formed by the strings. For each column, we compare the characters from top to bottom to ensure that they are in non-decreasing order. If a column is found to be unsorted, it needs to be deleted. We maintain a count of such unsorted columns and return this count at the end.
Time Complexity: O(m * n), where m is the number of strings and n is the length of each string. We iterate over each column and each row within the column.
Space Complexity: O(1), no additional space is used except for a few variables.
1#include <stdio.h>
2#include <string.h>
3
4int minDeletionSize(char **strs, int strsSize) {
5 int delCount = 0;
6 int columnCount = strlen(strs[0]);
7
8 for (int col = 0; col < columnCount; col++) {
9 for (int row = 1; row < strsSize; row++) {
10 if (strs[row][col] < strs[row - 1][col]) {
11 delCount++;
12 break;
13 }
14 }
15 }
16
17 return delCount;
18}
19
20int main() {
21 char *strs[] = {"cba", "daf", "ghi"};
22 int size = sizeof(strs) / sizeof(strs[0]);
23 printf("%d\n", minDeletionSize(strs, size));
24 return 0;
25}We start by computing the number of columns using the length of the first string. Then, we iterate over each column, and for each column, we check if it is sorted by comparing each element with its predecessor. If a descending pair is found, we increment the deletion count and break out of the loop for that column since it's unsorted.
In this approach, instead of checking each column individually with a nested loop, we try to reduce the checks by using internal helper functions or flags. This might reduce the overhead for checking conditions multiple times, though generally both approaches might occupy similar time complexity due to the input constraints.
Time Complexity: O(m * n)
Space Complexity: O(1)
1
public class Solution {
public int MinDeletionSize(string[] strs) {
int delCount = 0;
int columnCount = strs[0].Length;
for (int col = 0; col < columnCount; col++) {
bool sorted = true;
for (int row = 1; row < strs.Length && sorted; row++) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
sorted = false;
}
}
}
return delCount;
}
public static void Main(string[] args) {
string[] strs = {"cba", "daf", "ghi"};
Solution sol = new Solution();
Console.WriteLine(sol.MinDeletionSize(strs));
}
}In this C# example, early exits using a sorted flag help to optimize checking unnecessary parts of the input once an issue is detected.