944.删列造序

删列造序

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。这些字符串可以每个一行，排成一个网格。

对于有效的列索引 i，在第 i 列的所有字符从上到下必须按字典顺序排列。找出需要删除的列的最小数量，使剩余的列保持字典序。

示例 1:

输入：strs = [“cba”,”daf”,”ghi”]
输出：1

示例 2:

输入：strs = [“a”,”b”]
输出：0

提示:

• n == strs.length
• 1 <= n <= 100
• m == strs[i].length
• 1 <= m <= 100
• strs[i] 是小写字母

解析

遍历每一列，检查该列是否按字典序排列，不满足则计数加一。

var minDeletionSize = function (strs) {
  const m = strs.length;
  const n = strs[0].length;
  let deletions = 0;

  for (let col = 0; col < n; col++) {
    for (let row = 1; row < m; row++) {
      if (strs[row][col] < strs[row - 1][col]) {
        deletions++;
        break;
      }
    }
  }

  return deletions;
};

时间复杂度 O(m * n)，空间复杂度 O(1)。