960.删列造序 III

删列造序 III

给定字符串数组 strs，求保留最少的列使所有字符串按字典序排列。

示例 1:

输入：strs = [“ba”,”abcd”,”abca”,”cab”,”cad”]
输出：3

示例 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 n = strs.length;
  const m = strs[0].length;
  const keep = new Array(m).fill(true);

  for (let j = 1; j < m; j++) {
    for (let i = 1; i < n; i++) {
      if (!keep[j] && !keep[j - 1]) continue;
      if (strs[i][j] < strs[i][j - 1] && keep[j - 1]) {
        keep[j] = false;
        break;
      }
    }
  }

  return m - keep.filter(Boolean).length;
};

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