944.删列造序

链接：944.删列造序
难度：Easy
标签：数组、字符串
简介：给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。返回你需要删除的列数。

题解 1 - cpp

• 编辑时间：2022-03-25
• 执行用时：36ms
• 内存消耗：12MB
• 编程语言：cpp
• 解法介绍：按列遍历。

class Solution {
   public:
    int minDeletionSize(vector<string>& strs) {
        int ans = 0, n = strs.size(), m = strs[0].size();
        for (int i = 0; i < m; i++) {
            char prev = strs[0][i];
            for (int j = 1; j < n; j++) {
                if (strs[j][i] < prev) {
                    ans++;
                    break;
                }
                prev = strs[j][i];
            }
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-05-12
• 执行用时：52ms
• 内存消耗：12MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    int minDeletionSize(vector<string>& strs) {
        string prev = strs[0];
        int ans = 0;
        unordered_set<int> used;
        for (int i = 1; i < strs.size(); i++) {
            for (int j = 0; j < prev.size(); j++) {
                if (used.count(j)) continue;
                if (strs[i][j] < prev[j]) {
                    ans++;
                    used.insert(j);
                }
            }
            prev = strs[i];
        }
        return ans;
    }
};