944. Delete Columns to Make Sorted

leetcode easy

#array#csharp#easy#graph#leetcode#sort#string

Task

Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.

Пример:

Input: strs = ["cba","daf","ghi"]

Output: 1

C# solution

matched/original

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int count = 0;
        int rows = strs.Length;
        int cols = strs[0].Length;
        for (int col = 0; col < cols; col++) {
            for (int row = 1; row < rows; row++) {
                if (strs[row][col] < strs[row - 1][col]) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinDeletionSize(vector<string> strs) {
        int count = 0;
        int rows = strs.size();
        int cols = strs[0].size();
        for (int col = 0; col < cols; col++) {
            for (int row = 1; row < rows; row++) {
                if (strs[row][col] < strs[row - 1][col]) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

Java solution

matched/original

class Solution {
    public int minDeletionSize(String[] strs) {
        int count = 0;
        int rows = strs.length;
        int cols = strs[0].length();
        for (int col = 0; col < cols; col++) {
            for (int row = 1; row < rows; row++) {
                if (strs[row].charAt(col) < strs[row - 1].charAt(col)) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

JavaScript solution

matched/original

var minDeletionSize = function(strs) {
    let count = 0;
    for (let col = 0; col < strs[0].length; col++) {
        for (let row = 1; row < strs.length; row++) {
            if (strs[row][col] < strs[row - 1][col]) {
                count++;
                break;
            }
        }
    }
    return count;
};

Python solution

matched/original

def minDeletionSize(strs):
    count = 0
    for col in range(len(strs[0])):
        for row in range(1, len(strs)):
            if strs[row][col] < strs[row - 1][col]:
                count += 1
                break
    return count

Go solution

matched/original

package main

func minDeletionSize(strs []string) int {
    count := 0
    rows := len(strs)
    cols := len(strs[0])
    for col := 0; col < cols; col++ {
        for row := 1; row < rows; row++ {
            if strs[row][col] < strs[row-1][col] {
                count++
                break
            }
        }
    }
    return count
}

Explanation

Algorithm

Инициализировать переменную count для отслеживания количества столбцов, которые нужно удалить.

Пройти по каждому столбцу от 0 до длины строки.

Для каждого столбца проверить, отсортированы ли символы лексикографически.

Если столбец не отсортирован, увеличить count.

Вернуть count.

😎