Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

👨‍💻 Алгоритм:

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

2⃣Итеративно проверить каждую пару соседних строк для всех столбцов.
Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления.

3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.

😎 Решение:

class Solution {
    func minDeletionSize(_ strs: [String]) -> Int {
        let n = strs.count
        let m = strs[0].count
        var deleteCount = [Bool](repeating: false, count: m)
        
        func isSorted() -> Bool {
            for i in 0..<n - 1 {
                for j in 0..<m {
                    if deleteCount[j] { continue }
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] >
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        return false
                    }
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] <
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        break
                    }
                }
            }
            return true
        }
        
        while !isSorted() {
            for j in 0..<m {
                if deleteCount[j] { continue }
                for i in 0..<n - 1 {
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] >
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        deleteCount[j] = true
                        break
                    }
                }
                if deleteCount[j] { break }
            }
        }
        
        return deleteCount.filter { $0 }.count
    }
}

Ставь 👍 и забирай 📚 Базу знаний