经典算法题之删列造序（二）

解决方案

方法一：直接遍历思路和算法

题目要求删除不是按字典序升序排列的列，由于每个字符串的长度都相等，我们可以逐列访问字符串数组，统计不是按字典序升序排列的列。

对于第 j 列的字符串，我们需要检测所有相邻字符是否均满足 strs [ i−1 ] [ j ] ≤ strs [ i ][ j ]。

代码

Java

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

C++

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

C

int minDeletionSize(char ** strs, int strsSize) { int row = strsSize; int col = strlen(strs[0]); int ans = 0; for (int j = 0; j < col; ++j) { for (int i = 1; i < row; ++i) { if (strs[i - 1][j] > strs[i][j]) { ans++; break; } } } return ans; }

复杂度分析

时间复杂度：O(m×n)，其中 m 为字符串数组的长度，n 为数组中每个字符串的长度，判定每一列的的字典序需要遍历字符串数组每一列，因此时间复杂度为 O(m×n)。

空间复杂度：O(1)。