Проблема дня Leetcode [ 03 января 2023 ]
Вам дан массив из n
строк strs
одинаковой длины.
Строки можно расположить так, чтобы они были на каждой строке, образуя сетку. Например, strs = ["abc", "bce", "cae"]
можно расположить так:
abc bce cae
Вы хотите удалить столбцы, которые не отсортированы лексикографически. В приведенном выше примере (с индексом 0) столбцы 0 ('a'
, 'b'
, 'c'
) и 2 ('c'
, 'e'
, 'e'
) отсортированы, а столбец 1 ('b'
, 'c'
, 'a'
) — нет, поэтому вы должны удалить столбец 1.
Верните количество столбцов, которые вы удалите.
Пример 1:
Input: strs = ["cba","daf","ghi"] Output: 1 Explanation: The grid looks as follows: cba daf ghi Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.
Пример 2:
Input: strs = ["a","b"] Output: 0 Explanation: The grid looks as follows: a b Column 0 is the only column and is sorted, so you will not delete any columns.
Пример 3:
Input: strs = ["zyx","wvu","tsr"] Output: 3 Explanation: The grid looks as follows: zyx wvu tsr All 3 columns are not sorted, so you will delete all 3.
Решение
Для каждого индекса мы можем проверить, что все символы строки увеличиваются (больше предыдущего).
class Solution { public int minDeletionSize(String[] strs) { int n = strs.length; if(n == 0) return 0; int m = strs[0].length(); int ans = 0; for(int col=0;col<m;col++) { ans += notSorted(strs, col, n); } return ans; } public int notSorted(String[] strs, int col, int n) { for(int i=1;i<n;i++) { if(strs[i].charAt(col) < strs[i-1].charAt(col)) return 1; } return 0; } }
Временная сложность: O(N*M), где N — длина массива строк, а M — длина строки.
Космическая сложность: O(1)