Задача: 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⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.

😎 Решение:

function minDeletionSize($strs) {
    $n = count($strs);
    $m = strlen($strs[0]);
    $deleteCount = array_fill(0, $m, false);
    
    function isSorted($strs, $deleteCount) {
        $n = count($strs);
        $m = count($deleteCount);
        for ($i = 0; $i < $n - 1; $i++) {
            for ($j = 0; $j < $m; $j++) {
                if ($deleteCount[$j]) continue;
                if ($strs[$i][$j] > $strs[$i + 1][$j]) return false;
                if ($strs[$i][$j] < $strs[$i + 1][$j]) break;
            }
        }
        return true;
    }
    
    while (!isSorted($strs, $deleteCount)) {
        for ($j = 0; $j < $m; $j++) {
            if ($deleteCount[$j]) continue;
            for ($i = 0; $i < $n - 1; $i++) {
                if ($strs[$i][$j] > $strs[$i + 1][$j]) {
                    $deleteCount[$j] = true;
                    break;
                }
            }
            if ($deleteCount[$j]) break;
        }
    }
    
    return array_sum($deleteCount);
}

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