---
# System prepended metadata

title: 0955. Delete Columns to Make Sorted II
tags: [Leetcode, Medium, Greedy]

---

# 0955. Delete Columns to Make Sorted II
###### tags: `Leetcode` `Medium` `Greedy`
Link: https://leetcode.com/problems/delete-columns-to-make-sorted-ii/
## 思路 $O(MN)$ $O(N)$
N是字符串个数 M是字符串长度
对于strs[i]和strs[i+1]来说，如果strs[i]，strs[i+1]已经符合字典顺序，那么sorted[i]就是true，如果两个string已经是sorted了，就不要检查后面的字母了，否则就需要检查，如果不符合字母顺序，就要删除这一列 res++
## Code
```java=
class Solution {
    public int minDeletionSize(String[] strs) {
        int res = 0;
        boolean[] sorted = new boolean[strs.length];
        for(int i = 0; i < strs[0].length();i++){
            int j = 0;
            for(j = 0;j < strs.length-1;j++){
                if(!sorted[j] && strs[j].charAt(i) > strs[j+1].charAt(i)){
                    res++;
                    break;
                }
            }
            if(j < strs.length-1) continue;
            for(j = 0;j < strs.length-1;j++){
                sorted[j] |= strs[j].charAt(i) < strs[j+1].charAt(i);
            }
        }
        return res;
    }
}
```